Largest Odd Number in Numeric String - Visualization

Strings

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

Solution❯

Understanding the Problem

We are given a numeric string, and we need to find the largest odd number that exists as a prefix of this string. A prefix means we can only remove digits from the end of the string, not from the beginning or middle. Our goal is to return the longest prefix that ends in an odd digit (1, 3, 5, 7, 9). If there's no such prefix, we return an empty string.

Step-by-Step Solution with Example

Step 1: Start from the end of the string

We scan the string from right to left, checking each digit one by one. The reason we go from the end is because we are only allowed to remove digits from the end. So we’re looking for the last possible point where we can stop trimming.

Step 2: Check if a digit is odd

As we scan each digit, we check whether it is odd. The first time we find an odd digit, we stop. We then take the substring from the beginning of the string up to and including this digit.

Step 3: Return the substring

This substring is the largest odd number that can be formed from the original string by removing digits from the end.

Example: Input = "123456"

Let’s walk through this example.

  • Start from the end: 6 → even
  • Move left: 5 → odd

We found the last odd digit at index 4 (0-based). So, we take the substring from index 0 to 4. 

Result: "12345"

Edge Cases

All digits are even

Input: "24680"

There are no odd digits in the string. So, we can’t form any odd number.

Result: ""

Last digit is already odd

Input: "13579"

The last digit is odd, so the entire string is already the largest odd number.

Result: "13579"

Empty string

Input: ""

There is nothing to check, so we return an empty string.

Result: ""

Single odd digit

Input: "7"

It is already an odd number.

Result: "7"

Single even digit

Input: "8"

It is even, and there are no other digits.

Result: ""

Finally

This solution is simple and efficient. We don't need to convert the string into a number or use any advanced operations. Just a single backward scan of the string is enough. By checking from the rightmost digit and stopping at the first odd one, we ensure that the result is the longest possible odd prefix. This method is easy to follow and ideal for beginners learning string manipulation and basic conditions.

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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <string.h>

char* largestOddNumber(char num[]) {
    static char result[100];
    int len = strlen(num);
    for (int i = len - 1; i >= 0; i--) {
        if ((num[i] - '0') % 2 == 1) {
            strncpy(result, num, i + 1);
            result[i + 1] = '\0';
            return result;
        }
    }
    return "";
}

int main() {
    printf("%s\n", largestOddNumber("4206"));
    return 0;
}

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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...