Jobs

Interviews

Discussions

Maximum 69 Number

Easy

Asked by:

120 views

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.

Try coding it in LeetCode

Maximum 69 Number

Easy

Asked by:

120 views

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.

Try coding it in LeetCode

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:

The problem states the input is a positive integer represented as a string of digits, where each digit is either '6' or '9'. Can the input string be empty?
Are there any constraints on the length of the input string? For example, what is the maximum number of digits it can have?
Since the input is a string of '6's and '9's, does the string always contain at least one '6' to change to a '9'?
If the input string consists entirely of '9's, should I still attempt to change a digit, or is it implied that the input will always have at least one '6' available for modification?
What is the expected return format if the input string is empty or invalid in some way not covered by the '6' or '9' constraint?

Brute Force Solution

Approach

The idea here is to try making the number as large as possible by changing a 6 to a 9. The brute force way is to consider every single place you could possibly make that change and see which change results in the biggest number.

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

Look at the very first digit of the number.
Imagine changing that digit to a 9 (if it's currently a 6).
Calculate what the new number would be.
Now, move to the second digit of the original number.
Imagine changing that digit to a 9 (if it's currently a 6).
Calculate what this new number would be.
Continue this for every single digit in the original number, creating a new number each time you imagine changing a 6 to a 9.
After you've created all these new possible numbers, compare them all.
Pick the largest number from the ones you created.

Code Implementation

def maximum_69_number(number_to_process):
    string_representation_of_number = str(number_to_process)
    maximum_possible_number = number_to_process

    # Iterate through each digit to explore replacement possibilities
    for digit_index in range(len(string_representation_of_number)):
        # Only consider replacing a '6' to maximize the number
        if string_representation_of_number[digit_index] == '6':
            # Create a new string by replacing the '6' at the current index
            modified_number_string = list(string_representation_of_number)
            modified_number_string[digit_index] = '9'
            new_number = int("".join(modified_number_string))

            # Update the maximum if the newly formed number is larger
            if new_number > maximum_possible_number:
                maximum_possible_number = new_number

    return maximum_possible_number

Big(O) Analysis

Time Complexity

O(D) – The provided approach iterates through each digit of the input number. If the number has D digits, we perform a constant number of operations for each digit: checking if it's a 6, potentially creating a new number, and comparing it with the current maximum. Therefore, the total number of operations is directly proportional to the number of digits D in the input number. This results in a linear time complexity with respect to the number of digits, denoted as O(D).

Space Complexity

O(1) – The algorithm processes the number digit by digit without creating any auxiliary data structures that scale with the input number's size. Any variables used to store temporary results or the current maximum number are constant in size, regardless of the number of digits. Therefore, the auxiliary space complexity remains constant, independent of the input size N (number of digits).

Optimal Solution

Approach

The goal is to make the largest possible number by changing at most one digit. The key is to find the first '6' from the left and change it to a '9' to maximize the value.

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

Imagine the number as a sequence of digits.
Scan the digits from left to right.
The very first time you see a '6', change that '6' to a '9'.
Once you've made that single change, stop and the resulting number is the largest possible.
If you scan all the way to the end and don't find any '6's, then the original number is already the largest it can be, so you don't change anything.

Code Implementation

def maximum_six_nine(number_input):
    digits_of_number = list(str(number_input))
    found_six = False

    # Iterate from left to right to find the first '6'.
    for index, digit in enumerate(digits_of_number):
        # Changing the first '6' encountered maximizes the number.
        if digit == '6' and not found_six:
            digits_of_number[index] = '9'
            found_six = True
            # Once the change is made, stop to ensure only one digit is altered.
            break

    # Reconstruct the number from the modified digits.
    return int("".join(digits_of_number))

Big(O) Analysis

Time Complexity

O(L) – The solution involves iterating through the digits of the input number from left to right. Let L be the number of digits in the input number. In the worst case, we might need to scan all L digits to find the first '6' or to determine that no '6' exists. Each digit is examined at most once. Therefore, the total number of operations is directly proportional to the number of digits in the input, which results in a time complexity of O(L).

Space Complexity

O(1) – The provided plain English solution involves scanning the digits of the number and potentially performing a single replacement. This can be achieved using a fixed number of variables to track the current position and the modified number, irrespective of the input number's magnitude. No auxiliary data structures that grow with the input size N (number of digits) are created. Therefore, the auxiliary space complexity remains constant.

Edge Cases

Case	How to Handle
Input string is empty or null	The problem statement specifies a positive integer, so empty or null inputs are not expected; robust code might return an empty string or throw an error.
Input string contains only 9s	No 6s are present, so no change can be made; the original string should be returned.
Input string contains only 6s	The leftmost 6 should be changed to a 9 to maximize the number; this involves changing the first character.
Input string has a single digit	If the digit is 6, change it to 9; if it's 9, return it as is.
Input string contains mixed 6s and 9s	Iterate from left to right and change the first encountered 6 to a 9.
Very long input string	The solution should scale linearly with the length of the string, which is efficient for typical interview constraints.
Input string contains digits other than 6 or 9	The problem statement guarantees only 6s and 9s; unexpected characters would require validation or error handling.
Multiple 6s exist, which 6 to change?	To maximize the number, change the leftmost 6 to a 9, as this has the greatest positional value.

Input string is empty or null

How to Handle:

The problem statement specifies a positive integer, so empty or null inputs are not expected; robust code might return an empty string or throw an error.

Input string contains only 9s

How to Handle:

No 6s are present, so no change can be made; the original string should be returned.

Input string contains only 6s

How to Handle:

The leftmost 6 should be changed to a 9 to maximize the number; this involves changing the first character.

Input string has a single digit

How to Handle:

If the digit is 6, change it to 9; if it's 9, return it as is.

Input string contains mixed 6s and 9s

How to Handle:

Iterate from left to right and change the first encountered 6 to a 9.

Very long input string

How to Handle:

The solution should scale linearly with the length of the string, which is efficient for typical interview constraints.

Input string contains digits other than 6 or 9

How to Handle:

The problem statement guarantees only 6s and 9s; unexpected characters would require validation or error handling.

Multiple 6s exist, which 6 to change?

How to Handle:

To maximize the number, change the leftmost 6 to a 9, as this has the greatest positional value.

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:

The problem states the input is a positive integer represented as a string of digits, where each digit is either '6' or '9'. Can the input string be empty?
Are there any constraints on the length of the input string? For example, what is the maximum number of digits it can have?
Since the input is a string of '6's and '9's, does the string always contain at least one '6' to change to a '9'?
If the input string consists entirely of '9's, should I still attempt to change a digit, or is it implied that the input will always have at least one '6' available for modification?
What is the expected return format if the input string is empty or invalid in some way not covered by the '6' or '9' constraint?

Brute Force Solution

Approach

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

Look at the very first digit of the number.
Imagine changing that digit to a 9 (if it's currently a 6).
Calculate what the new number would be.
Now, move to the second digit of the original number.
Imagine changing that digit to a 9 (if it's currently a 6).
Calculate what this new number would be.
Continue this for every single digit in the original number, creating a new number each time you imagine changing a 6 to a 9.
After you've created all these new possible numbers, compare them all.
Pick the largest number from the ones you created.

Code Implementation

def maximum_69_number(number_to_process):
    string_representation_of_number = str(number_to_process)
    maximum_possible_number = number_to_process

    # Iterate through each digit to explore replacement possibilities
    for digit_index in range(len(string_representation_of_number)):
        # Only consider replacing a '6' to maximize the number
        if string_representation_of_number[digit_index] == '6':
            # Create a new string by replacing the '6' at the current index
            modified_number_string = list(string_representation_of_number)
            modified_number_string[digit_index] = '9'
            new_number = int("".join(modified_number_string))

            # Update the maximum if the newly formed number is larger
            if new_number > maximum_possible_number:
                maximum_possible_number = new_number

    return maximum_possible_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to make the largest possible number by changing at most one digit. The key is to find the first '6' from the left and change it to a '9' to maximize the value.

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

Imagine the number as a sequence of digits.
Scan the digits from left to right.
The very first time you see a '6', change that '6' to a '9'.
Once you've made that single change, stop and the resulting number is the largest possible.
If you scan all the way to the end and don't find any '6's, then the original number is already the largest it can be, so you don't change anything.

Code Implementation

def maximum_six_nine(number_input):
    digits_of_number = list(str(number_input))
    found_six = False

    # Iterate from left to right to find the first '6'.
    for index, digit in enumerate(digits_of_number):
        # Changing the first '6' encountered maximizes the number.
        if digit == '6' and not found_six:
            digits_of_number[index] = '9'
            found_six = True
            # Once the change is made, stop to ensure only one digit is altered.
            break

    # Reconstruct the number from the modified digits.
    return int("".join(digits_of_number))

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input string is empty or null	The problem statement specifies a positive integer, so empty or null inputs are not expected; robust code might return an empty string or throw an error.
Input string contains only 9s	No 6s are present, so no change can be made; the original string should be returned.
Input string contains only 6s	The leftmost 6 should be changed to a 9 to maximize the number; this involves changing the first character.
Input string has a single digit	If the digit is 6, change it to 9; if it's 9, return it as is.
Input string contains mixed 6s and 9s	Iterate from left to right and change the first encountered 6 to a 9.
Very long input string	The solution should scale linearly with the length of the string, which is efficient for typical interview constraints.
Input string contains digits other than 6 or 9	The problem statement guarantees only 6s and 9s; unexpected characters would require validation or error handling.
Multiple 6s exist, which 6 to change?	To maximize the number, change the leftmost 6 to a 9, as this has the greatest positional value.

Input string is empty or null

How to Handle:

The problem statement specifies a positive integer, so empty or null inputs are not expected; robust code might return an empty string or throw an error.

Input string contains only 9s

How to Handle:

No 6s are present, so no change can be made; the original string should be returned.

Input string contains only 6s

How to Handle:

The leftmost 6 should be changed to a 9 to maximize the number; this involves changing the first character.

Input string has a single digit

How to Handle:

If the digit is 6, change it to 9; if it's 9, return it as is.

Input string contains mixed 6s and 9s

How to Handle:

Iterate from left to right and change the first encountered 6 to a 9.

Very long input string

How to Handle:

The solution should scale linearly with the length of the string, which is efficient for typical interview constraints.

Input string contains digits other than 6 or 9

How to Handle:

The problem statement guarantees only 6s and 9s; unexpected characters would require validation or error handling.

Multiple 6s exist, which 6 to change?

How to Handle:

To maximize the number, change the leftmost 6 to a 9, as this has the greatest positional value.