We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Odd Number in String

Number: 2032

Difficulty: Easy

Paid? No

Companies: Google, Meta, Amazon, Adobe, Apple

Problem Description

Given a string representing a large integer, return the largest-valued odd integer (as a string) that is a contiguous substring of the input string. If no odd digit exists in the string, return an empty string.

Key Insights

  • The largest odd integer, in value, can be obtained by using as many digits from the start as possible until the last odd digit.
  • Traversing the string from right to left to find the last occurrence of an odd digit ensures keeping the most significant digits intact.
  • If no odd digit is encountered, the result should be an empty string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string (single reverse scan).
Space Complexity: O(n) in the worst case for the substring output, with O(1) additional space.

Solution

The solution involves scanning the given number string from right to left, searching for the first odd digit encountered. Once an odd digit is found, the substring from the beginning of the string up to that digit (inclusive) is returned. This guarantees the largest odd number since removing any digits from the left would result in a smaller number, and using any substring not starting from the beginning would omit critical digits. If no odd digit is found, the function returns an empty string.

Code Solutions

# Function to return the largest odd number substring
def largestOddNumber(num: str) -> str:
    # Traverse from the end of the string to the beginning
    for i in range(len(num) - 1, -1, -1):
        # Check if the current digit is odd by converting to integer and using modulo 2
        if int(num[i]) % 2 == 1:
            # Return the substring from the beginning up to and including the odd digit
            return num[:i+1]
    # If no odd digit is found, return an empty string
    return ""

# Example usage
print(largestOddNumber("52"))    # Output: "5"
print(largestOddNumber("4206"))  # Output: ""
print(largestOddNumber("35427")) # Output: "35427"
← Back to All Questions