Jobs

Interviews

Discussions

Maximum 69 Number

Easy

Hudson River Trading

1 view

Topics:

ArraysGreedy Algorithms

You are given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Constraints:

1 <= num <= 10⁴
num consists of only 6 and 9 digits.

Maximum 69 Number

Easy

Hudson River Trading

1 view

Topics:

ArraysGreedy Algorithms

You are given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Constraints:

1 <= num <= 10⁴
num consists of only 6 and 9 digits.

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:

What is the maximum possible value of the input integer num?
Is the input guaranteed to contain only the digits 6 and 9?
If I change a digit, should I change the leftmost possible 6 to a 9 to maximize the result, or is any change acceptable?
Is the input always a positive number?
Is it possible for the input to be a single digit number?

Brute Force Solution

Approach

The brute force approach involves checking every possible change we can make to the number. We'll try flipping each 6 to a 9, one at a time, and keep track of which flip gives us the largest possible number.

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

Look at the number from left to right.
Find the first 6. If there isn't one, there's nothing to do.
Pretend to change that 6 to a 9 and see what number you get.
Now, go back to the original number and find the second 6 (if there is one). Pretend to change that one to a 9 and see what you get.
Keep doing this for every 6 in the number, each time pretending to change only that 6 to a 9.
After you have tried changing each 6 to a 9 separately, compare all the numbers you got. The biggest one is your answer.

Code Implementation

def maximum_69_number_brute_force(number):
    number_string = str(number)
    maximum_number = number

    # Iterate to find each '6' to potentially replace
    for index in range(len(number_string)):
        if number_string[index] == '6':
            # Create a new number string with the flipped digit
            modified_number_string = list(number_string)
            modified_number_string[index] = '9'
            modified_number = int("".join(modified_number_string))

            # Check if this flip created a larger number
            if modified_number > maximum_number:
                maximum_number = modified_number

    return maximum_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the number (represented as a string). In the worst-case scenario, it iterates once to find the leftmost '6'. If a '6' is found, it creates a modified string, which takes O(n) in some implementations, but can be optimized. However, since we only modify one digit at most and don't have nested loops dependent on n, the dominant operation is iterating through the string to find the first '6'. Therefore, the time complexity is O(n), where n is the number of digits in the input number.

Space Complexity

O(1) – The provided approach involves iterating through the number and temporarily modifying it to check the result of changing a '6' to a '9'. It does not create any additional data structures like arrays, lists, or hash maps to store intermediate results. The only extra space used would be for a few variables to store the original number and the potentially modified number. These variables consume a constant amount of space irrespective of the input number's size, N, making the auxiliary space complexity O(1).

Optimal Solution

Approach

The goal is to find the largest possible number by changing at most one digit in the given number. The clever trick is to only consider changing the leftmost '6' to a '9', because doing so will always yield the largest possible increase in the number's value.

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

Look at the number from left to right.
Find the first occurrence of the digit '6'.
If you find a '6', change it to a '9'.
If you don't find any '6's, then there's nothing to change, and the original number is already the maximum possible.
The resulting number (either from changing the '6' or the original number) is the answer.

Code Implementation

def maximum69Number(number):
    number_string = str(number)
    
    # Iterate through the digits to find the leftmost '6'
    for index, digit in enumerate(number_string):
        if digit == '6':
            # Change the first '6' to '9'
            modified_number_string = number_string[:index] + '9' + number_string[index+1:]

            # Return the modified number as an integer
            return int(modified_number_string)

    # If no '6' is found, return the original number
    return number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the input number once, from left to right, to find the first occurrence of the digit '6'. The input size, n, represents the number of digits in the input. The cost is driven by the necessity to examine each digit in the number until a '6' is found, or the entire number is traversed. In the worst case, where there is no '6' or the '6' is at the very end, we examine all n digits. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input number (treated as a string) to find the leftmost '6'. It potentially modifies a character in place or returns the original number. No auxiliary data structures like arrays, lists, or hashmaps are created. Therefore, the space complexity is constant, independent of the input number's length (N). The algorithm only uses a few constant-sized variables.

Edge Cases

Case	How to Handle
Input is a single digit 6	The solution should change it to 9 and return 9.
Input is a single digit 9	The solution should return 9 as no change results in a larger number.
Input consists of all 9s	The solution should return the original number as no change makes it larger.
Input consists of all 6s	The solution should change the first 6 to a 9 to maximize the number.
Input starts with 6 followed by only 9s	Changing the first 6 to 9 will provide the largest possible outcome.
Integer Overflow after changing a digit	This is not applicable since the number of digits is relatively small and conversion back to integer will not lead to overflow.
Input contains leading zeros (though not explicitly disallowed by prompt)	Treat the input as a number and leading zeros are implicitly dropped; the algorithm proceeds as normal.
Maximum integer value consisting of only 6s and 9s (close to Integer.MAX_VALUE)	The algorithm modifies at most one digit, so it won't exceed the maximum integer value representable.

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:

What is the maximum possible value of the input integer num?
Is the input guaranteed to contain only the digits 6 and 9?
If I change a digit, should I change the leftmost possible 6 to a 9 to maximize the result, or is any change acceptable?
Is the input always a positive number?
Is it possible for the input to be a single digit number?

Brute Force Solution

Approach

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

Look at the number from left to right.
Find the first 6. If there isn't one, there's nothing to do.
Pretend to change that 6 to a 9 and see what number you get.
Now, go back to the original number and find the second 6 (if there is one). Pretend to change that one to a 9 and see what you get.
Keep doing this for every 6 in the number, each time pretending to change only that 6 to a 9.
After you have tried changing each 6 to a 9 separately, compare all the numbers you got. The biggest one is your answer.

Code Implementation

def maximum_69_number_brute_force(number):
    number_string = str(number)
    maximum_number = number

    # Iterate to find each '6' to potentially replace
    for index in range(len(number_string)):
        if number_string[index] == '6':
            # Create a new number string with the flipped digit
            modified_number_string = list(number_string)
            modified_number_string[index] = '9'
            modified_number = int("".join(modified_number_string))

            # Check if this flip created a larger number
            if modified_number > maximum_number:
                maximum_number = modified_number

    return maximum_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Look at the number from left to right.
Find the first occurrence of the digit '6'.
If you find a '6', change it to a '9'.
If you don't find any '6's, then there's nothing to change, and the original number is already the maximum possible.
The resulting number (either from changing the '6' or the original number) is the answer.

Code Implementation

def maximum69Number(number):
    number_string = str(number)
    
    # Iterate through the digits to find the leftmost '6'
    for index, digit in enumerate(number_string):
        if digit == '6':
            # Change the first '6' to '9'
            modified_number_string = number_string[:index] + '9' + number_string[index+1:]

            # Return the modified number as an integer
            return int(modified_number_string)

    # If no '6' is found, return the original number
    return number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is a single digit 6	The solution should change it to 9 and return 9.
Input is a single digit 9	The solution should return 9 as no change results in a larger number.
Input consists of all 9s	The solution should return the original number as no change makes it larger.
Input consists of all 6s	The solution should change the first 6 to a 9 to maximize the number.
Input starts with 6 followed by only 9s	Changing the first 6 to 9 will provide the largest possible outcome.
Integer Overflow after changing a digit	This is not applicable since the number of digits is relatively small and conversion back to integer will not lead to overflow.
Input contains leading zeros (though not explicitly disallowed by prompt)	Treat the input as a number and leading zeros are implicitly dropped; the algorithm proceeds as normal.
Maximum integer value consisting of only 6s and 9s (close to Integer.MAX_VALUE)	The algorithm modifies at most one digit, so it won't exceed the maximum integer value representable.