Largest Odd Number in Numeric String

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given a numeric string (i.e., a string that contains only digits), your task is to extract the largest-valued odd number that can be formed by removing some digits from the end of the string.

  • The resulting number must be a prefix of the original string.
  • If no such odd number exists, return an empty string "".

Remember, a number is odd if it ends with 1, 3, 5, 7, or 9.

Examples❯

Input Output Description
"35427" 35427 Entire number is odd; last digit is 7 (odd)
"4206" "" No odd digits in the string
"12540" 125 Last odd digit is 5 at index 2; return prefix up to index 2
"8080" "" All digits are even; return empty string
"1001" 1001 Last digit is 1 (odd); entire string is valid
"1000" 1 Last odd digit is 1 at index 0
"1" 1 Single-digit odd number
"4" "" Single-digit even number
"" "" Empty string input returns empty string

Visualization Player

Solution❯

To solve this problem, we need to find the largest odd number that exists as a prefix of the given numeric string. Let's break it down in simple terms.

We are only allowed to remove digits from the end of the string. That means, we can keep shortening the number from the right side until we find a version that ends with an odd digit.

Case 1: Last digit is odd

If the last digit of the string is odd (like 1, 3, 5, 7, or 9),

{ "array": [1, 2, 3, 4, 5], "showIndices": false, "highlightIndicesGreen": [4] }

then the entire string is already an odd number. We simply return the whole string.

{ "array": [1, 2, 3, 4, 5], "showIndices": false, "highlightIndicesGreen": [0,1,2,3,4] }

Case 2: Last digit is even, but there is an odd digit earlier

If the string ends in an even digit (like 0, 2, 4, 6, 8), we move leftward to find the last occurrence of an odd digit.

{ "array": [1, 2, 3, 4, 6], "showIndices": false, "highlightIndicesGreen": [2] }

The moment we find it, we return the substring from the beginning up to that digit (inclusive). This is the largest odd number that can be formed as a prefix.

{ "array": [1, 2, 3, 4, 6], "showIndices": false, "highlightIndicesGreen": [0,1,2] }

Case 3: No odd digit at all

If the string doesn't contain any odd digits, there is no way to form an odd number.

{ "array": [4, 2, 6, 4, 8], "showIndices": false, "highlightIndicesGreen": [] }

In this case, we return an empty string "".

Case 4: Edge case - Empty string

If the input is an empty string, we also return "" since there's nothing to check.

This approach is simple, efficient, and beginner-friendly because we are just scanning the string from the end until we find what we need. There’s no need to convert anything to an actual number or use complex operations.

Algorithm Steps❯

  1. Start from the end of the string and move backward.
  2. Check each character:
  3. → If it's an odd digit (1, 3, 5, 7, 9), take the substring from the beginning to that character (inclusive).
  4. → Return this substring immediately as it's the largest odd number possible.
  5. If no odd digit is found, return an empty string "".

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
def largest_odd_number(num):
    for i in range(len(num) - 1, -1, -1):
        if int(num[i]) % 2 == 1:
            return num[:i + 1]  # Return the substring ending at the last odd digit
    return ""  # No odd digit found

# Sample Input
print(largest_odd_number("4206"))  # Output: ""

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(1)If the last character is odd, we return immediately.
Average CaseO(n)In the average case, we might scan most of the string to find the last odd digit.
Worst CaseO(n)If no odd digit is present, the entire string is scanned once.

Space Complexity

O(1)

Explanation: We use a constant number of variables, and only return a substring from the original input.