Problem Description

You are given a positive integer num that contains only the digits 6 and 9.

Your task is to find the maximum number you can create by changing at most one digit in the number. You can change a 6 to a 9, or change a 9 to a 6.

For example:

• If num = 9669, you can change the first 6 to get 9969, which is the maximum possible
• If num = 9996, you can change the last 6 to get 9999
• If num = 9999, you don't need to change anything since it's already the maximum

The solution uses a greedy approach: to maximize the number, we want to change the leftmost 6 to a 9 (if any exists). This is because changing a digit in a more significant position has a greater impact on the final value. The code converts the number to a string, replaces the first occurrence of "6" with "9" using replace("6", "9", 1) where the third parameter 1 ensures only the first 6 is replaced, then converts back to an integer.

Intuition

To maximize a number, we want the leftmost (most significant) digits to be as large as possible. Since our number only contains 6 and 9, and 9 is larger than 6, we want as many 9s as possible, especially in the higher-value positions.

When we can change at most one digit, we need to decide which digit change would give us the biggest increase. Changing a 6 to a 9 increases the value, while changing a 9 to a 6 decreases it. So we should only consider changing 6 to 9.

But which 6 should we change if there are multiple? Consider these examples:

• Changing 6669 → the first 6 gives us 9669 (increase of 3000)
• Changing 6669 → the second 6 gives us 6969 (increase of 300)
• Changing 6669 → the third 6 gives us 6699 (increase of 30)

The pattern is clear: changing a digit in a higher position gives a larger increase. The leftmost 6 represents the highest place value among all 6s in the number, so changing it to 9 will give us the maximum possible increase.

If the number contains no 6s (like 9999), then we can't improve it further, and the original number is already the maximum.

This leads us to the simple strategy: find the first 6 from the left and change it to 9. If there's no 6, keep the number as is.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows a straightforward greedy approach by converting the number to a string for easy manipulation:

1. Convert number to string: We first convert the integer num to a string using str(num). This allows us to easily access and manipulate individual digits.

2. Find and replace the first '6': We use Python's replace() method with the syntax replace("6", "9", 1). The key parameters are:

   • First parameter "6": the character to search for
   • Second parameter "9": the character to replace it with
   • Third parameter 1: limits the replacement to only the first occurrence

   This ensures we only change the leftmost 6 to 9, which gives us the maximum possible value.

3. Convert back to integer: After the replacement, we convert the resulting string back to an integer using int().

The beauty of this solution lies in its simplicity. The replace() method with the limit parameter handles all the logic:

• If there's at least one 6, it replaces only the first one (leftmost)
• If there are no 6s in the number, the string remains unchanged
• No need for loops or conditional statements

Time Complexity: O(n) where n is the number of digits, as we need to convert to string and potentially scan for the first 6.

Space Complexity: O(n) for storing the string representation of the number.

This one-liner solution elegantly captures the greedy strategy: maximize the number by changing the most significant 6 to 9.

Example Walkthrough

Let's walk through the solution with num = 6996:

Step 1: Convert to string

• num = 6996 becomes "6996"

Step 2: Find the first '6' and replace with '9'

• Scanning from left to right, the first '6' is at position 0
• Using replace("6", "9", 1):
  • The method searches for "6" in the string "6996"
  • It finds the first occurrence at index 0
  • It replaces only this first "6" with "9" (due to the limit parameter 1)
  • Result: "9996"

Step 3: Convert back to integer

• "9996" becomes 9996

Why this gives the maximum:

• Original number: 6996
• If we changed the first '6' → 9996 (increase of 3000) ✓ This is what we did
• If we changed the second '6' → 6996 (no change, same position)
• If we changed any '9' to '6' → would decrease the value

The algorithm correctly identifies that changing the leftmost '6' to '9' produces the maximum value of 9996.

Another example with no changes needed: For num = 9999:

• Convert to string: "9999"
• Try to replace first '6' with '9': No '6' found, string remains "9999"
• Convert back: 9999
• The number stays the same, which is correct since it's already maximized.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log num)

The time complexity is determined by the following operations:

• Converting the integer num to a string: O(log num) - the number of digits in num is proportional to log num
• The replace() method with limit 1: O(log num) - it needs to scan through the string until it finds the first '6' or reaches the end
• Converting the string back to an integer: O(log num)

Since all operations are O(log num) and they're performed sequentially, the overall time complexity is O(log num).

Space Complexity: O(log num)

The space complexity comes from:

• Creating a string representation of num: O(log num) - the string length equals the number of digits
• The replace() method creates a new string: O(log num) - Python strings are immutable, so a new string of the same length is created
• The intermediate string objects before conversion back to integer

Therefore, the space complexity is O(log num) as we need to store strings with length proportional to the number of digits in num.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Replace Multiple Digits

A common misunderstanding is thinking we need to replace ALL occurrences of '6' with '9' to maximize the number. This would be incorrect since the problem states we can change "at most one digit."

Incorrect approach:

# Wrong: This replaces ALL '6's with '9's
def maximum69Number(self, num: int) -> int:
    return int(str(num).replace("6", "9"))  # Missing the count parameter

Why it fails: For num = 6669, this would return 9999 instead of the correct answer 9669 (only the first '6' should be changed).

Solution: Always use the count parameter in replace() method: replace("6", "9", 1)

2. Trying to Change '9' to '6' When No '6' Exists

Some might think that if there are no '6's in the number, we should change a '9' to '6'. This is incorrect because changing any '9' to '6' would decrease the number, not maximize it.

Incorrect logic:

def maximum69Number(self, num: int) -> int:
    num_str = str(num)
    if '6' in num_str:
        return int(num_str.replace("6", "9", 1))
    else:
        # Wrong: Don't change '9' to '6'
        return int(num_str.replace("9", "6", 1))

Why it fails: For num = 9999, this would return 6999 which is smaller than the original.

Solution: The problem asks for "at most one" change, meaning zero changes is valid. If there are no '6's, leave the number unchanged.

3. Replacing the Wrong '6' (Not the Leftmost)

Using complex logic to find and replace a '6' other than the leftmost one, perhaps thinking about replacing the "largest" '6' or using different criteria.

Incorrect approach:

def maximum69Number(self, num: int) -> int:
    num_str = str(num)
    # Wrong: Replacing the last '6' instead of the first
    if '6' in num_str:
        idx = num_str.rfind('6')  # Finds rightmost '6'
        num_str = num_str[:idx] + '9' + num_str[idx+1:]
    return int(num_str)

Why it fails: For num = 6996, this would return 6999 instead of the correct answer 9996.

Solution: Always replace the leftmost (first) '6' since changing a more significant digit has a greater impact on the final value.