Jobs

Interviews

Discussions

Largest Odd Number in String

Easy

Amazon

2 views

Topics:

Strings

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

For example:

If num = "52", the output should be "5". The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.
If num = "4206", the output should be "". There are no odd numbers in "4206".
If num = "35427", the output should be "35427". "35427" is already an odd number.

Write a function that takes a string num as input and returns the largest-valued odd integer substring, or an empty string if none exists. Consider the edge cases such as when the input string contains only even numbers, or when the entire input string is already an odd number. Optimize for time and space complexity.

Largest Odd Number in String

Easy

Amazon

2 views

Topics:

Strings

A substring is a contiguous sequence of characters within a string.

For example:

If num = "52", the output should be "5". The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.
If num = "4206", the output should be "". There are no odd numbers in "4206".
If num = "35427", the output should be "35427". "35427" is already an odd number.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `num` contain leading zeros?
What should be returned if the input string `num` does not contain any odd digits?
Are there any specific constraints on the length of the input string `num`?
Is the input string guaranteed to contain only numerical digits, or can it contain other characters?
If multiple odd numbers of the same length exist as substrings from the beginning, should I return the first one encountered, or is there another criterion for selecting amongst them?

Brute Force Solution

Approach

The brute force way to find the largest odd number in a string is like trying every possible ending. We'll start from the full string and keep chopping off characters from the right until we find an odd number.

Here's how the algorithm would work step-by-step:

Begin with the entire string.
Check if the last digit of the string is an odd number (1, 3, 5, 7, or 9).
If the last digit is odd, then you've found the largest odd number, and you're done!
If the last digit is even, remove the last digit from the string.
Now, check if the new last digit (of the shortened string) is odd.
Keep removing digits from the right one at a time and checking the last digit until you find an odd number or the string becomes empty.
If the string becomes empty, it means there are no odd numbers in the original string.

Code Implementation

def largest_odd_number_in_string_brute_force(number):
    string_length = len(number)

    # Iterate from the end of the string to the beginning
    for i in range(string_length, 0, -1):
        substring = number[:i]
        last_digit_string = substring[-1]

        # Check if the last digit is odd
        last_digit = int(last_digit_string)
        if last_digit % 2 != 0:

            #If it is, return the substring
            return substring

    # If no odd digit is found, return an empty string
    return ""

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 'num' from right to left. In each iteration, it checks if the rightmost digit is odd. If it's odd, the algorithm terminates immediately. If it's even, the algorithm removes the rightmost digit. Therefore, in the worst-case scenario, the algorithm iterates through the entire string once. Thus, the time complexity is directly proportional to the length of the string, which we denote as 'n'. Hence, the time complexity is O(n).

Space Complexity

O(1) – The algorithm modifies the input string in place by repeatedly shortening it. No additional data structures like lists, hash maps, or arrays are created. The operations only involve checking the last character and potentially truncating the string, which doesn't consume extra memory proportional to the input size N, where N is the length of the input string. Therefore, the auxiliary space used is constant.

Optimal Solution

Approach

The goal is to find the largest odd number that's a substring of the given string. Instead of checking all possible substrings, we'll work backwards from the end of the string to find the first odd digit.

Here's how the algorithm would work step-by-step:

Start by examining the last digit of the number.
If the last digit is odd, you've found your answer; it's the whole number.
If the last digit is even, remove the last digit and look at the new last digit.
Repeat the process of removing the last digit until you find an odd digit or you run out of digits.
If you find an odd digit, the substring from the beginning of the number up to and including that odd digit is the answer.
If you run out of digits without finding an odd digit, then there is no odd number in the string, so the answer is an empty string.

Code Implementation

def largestOddNumber(number: str) -> str:
    for i in range(len(number) - 1, -1, -1):
        # Check digits from right to left for oddness.
        current_digit = int(number[i])

        if current_digit % 2 != 0:
            # If odd, return the substring up to and including this digit.
            return number[:i+1]

    # If no odd digit is found return empty string.
    return ""

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string 'num' from right to left, at most once, until it finds an odd digit. In the worst-case scenario, it iterates through the entire string. Therefore, the time complexity is directly proportional to the length of the string, 'n', representing the number of digits in the input number. This leads to a linear relationship making the time complexity O(n).

Space Complexity

O(1) – The provided algorithm iterates through the string, potentially shortening it by removing the last digit. It does not create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results. The only memory used is for loop variables or temporary variables used in comparisons or string slicing, which takes constant space regardless of the input string's length N. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string if the input is null or empty since no odd number can exist.
String contains no odd digits	Iterate from right to left; if no odd digit is found, the loop completes and return empty string.
String with a single digit, which is odd	Return the single-digit string as it is the largest odd number.
String with a single digit, which is even	Return an empty string since no odd digit is present.
String consists only of even digits	Return an empty string because there's no odd number to be extracted.
String with leading zeros	The algorithm should correctly process leading zeros as part of the string and return the substring up to the last odd digit.
String with a very long sequence of even digits followed by a single odd digit	The right-to-left iteration will efficiently find the odd digit without iterating through the entire string if possible.
Maximum length string consisting of odd numbers	Algorithm scales linearly with string length, so should handle maximum-length input without significant performance issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `num` contain leading zeros?
What should be returned if the input string `num` does not contain any odd digits?
Are there any specific constraints on the length of the input string `num`?
Is the input string guaranteed to contain only numerical digits, or can it contain other characters?
If multiple odd numbers of the same length exist as substrings from the beginning, should I return the first one encountered, or is there another criterion for selecting amongst them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin with the entire string.
Check if the last digit of the string is an odd number (1, 3, 5, 7, or 9).
If the last digit is odd, then you've found the largest odd number, and you're done!
If the last digit is even, remove the last digit from the string.
Now, check if the new last digit (of the shortened string) is odd.
Keep removing digits from the right one at a time and checking the last digit until you find an odd number or the string becomes empty.
If the string becomes empty, it means there are no odd numbers in the original string.

Code Implementation

def largest_odd_number_in_string_brute_force(number):
    string_length = len(number)

    # Iterate from the end of the string to the beginning
    for i in range(string_length, 0, -1):
        substring = number[:i]
        last_digit_string = substring[-1]

        # Check if the last digit is odd
        last_digit = int(last_digit_string)
        if last_digit % 2 != 0:

            #If it is, return the substring
            return substring

    # If no odd digit is found, return an empty string
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by examining the last digit of the number.
If the last digit is odd, you've found your answer; it's the whole number.
If the last digit is even, remove the last digit and look at the new last digit.
Repeat the process of removing the last digit until you find an odd digit or you run out of digits.
If you find an odd digit, the substring from the beginning of the number up to and including that odd digit is the answer.
If you run out of digits without finding an odd digit, then there is no odd number in the string, so the answer is an empty string.

Code Implementation

def largestOddNumber(number: str) -> str:
    for i in range(len(number) - 1, -1, -1):
        # Check digits from right to left for oddness.
        current_digit = int(number[i])

        if current_digit % 2 != 0:
            # If odd, return the substring up to and including this digit.
            return number[:i+1]

    # If no odd digit is found return empty string.
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string if the input is null or empty since no odd number can exist.
String contains no odd digits	Iterate from right to left; if no odd digit is found, the loop completes and return empty string.
String with a single digit, which is odd	Return the single-digit string as it is the largest odd number.
String with a single digit, which is even	Return an empty string since no odd digit is present.
String consists only of even digits	Return an empty string because there's no odd number to be extracted.
String with leading zeros	The algorithm should correctly process leading zeros as part of the string and return the substring up to the last odd digit.
String with a very long sequence of even digits followed by a single odd digit	The right-to-left iteration will efficiently find the odd digit without iterating through the entire string if possible.
Maximum length string consisting of odd numbers	Algorithm scales linearly with string length, so should handle maximum-length input without significant performance issues.