Find the Largest Odd Number in a Numeric String

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.

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.

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 "".

#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;
}

#include <iostream>
#include <string>
using namespace std;

string largestOddNumber(string num) {
    for (int i = num.length() - 1; i >= 0; i--) {
        if ((num[i] - '0') % 2 == 1) {
            return num.substr(0, i + 1);
        }
    }
    return "";
}

int main() {
    cout << largestOddNumber("4206") << endl;
    return 0;
}

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 ""

print(largest_odd_number("4206"))

public class LargestOddNumber {
    public static String largestOddNumber(String num) {
        for (int i = num.length() - 1; i >= 0; i--) {
            if ((num.charAt(i) - '0') % 2 == 1) {
                return num.substring(0, i + 1);
            }
        }
        return "";
    }

    public static void main(String[] args) {
        System.out.println(largestOddNumber("4206"));
    }
}

function largestOddNumber(num) {
    for (let i = num.length - 1; i >= 0; i--) {
        if (parseInt(num[i]) % 2 === 1) {
            return num.substring(0, i + 1);
        }
    }
    return "";
}

console.log(largestOddNumber("4206"));

package main

import (
    "fmt"
)

func largestOddNumber(num string) string {
    for i := len(num) - 1; i >= 0; i-- {
        if (num[i]-'0')%2 == 1 {
            return num[:i+1]
        }
    }
    return ""
}

func main() {
    fmt.Println(largestOddNumber("4206"))
}

fn largest_odd_number(num: &str) -> &str {
    for i in (0..num.len()).rev() {
        if let Some(c) = num.chars().nth(i) {
            if c.to_digit(10).unwrap() % 2 == 1 {
                return &num[..=i];
            }
        }
    }
    ""
}

fn main() {
    println!("{}", largest_odd_number("4206"));
}

fun largestOddNumber(num: String): String {
    for (i in num.length - 1 downTo 0) {
        if ((num[i] - '0') % 2 == 1) {
            return num.substring(0, i + 1)
        }
    }
    return ""
}

fun main() {
    println(largestOddNumber("4206"))
}

func largestOddNumber(_ num: String) -> String {
    for i in stride(from: num.count - 1, through: 0, by: -1) {
        let index = num.index(num.startIndex, offsetBy: i)
        if let digit = Int(String(num[index])), digit % 2 == 1 {
            return String(num.prefix(i + 1))
        }
    }
    return ""
}

print(largestOddNumber("4206"))

function largestOddNumber(num: string): string {
    for (let i = num.length - 1; i >= 0; i--) {
        if (parseInt(num[i]) % 2 === 1) {
            return num.substring(0, i + 1);
        }
    }
    return "";
}

console.log(largestOddNumber("4206"));

Time complexity

Space complexity

O(1)

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