Maximum 69 Number

Difficulty: Easy | Acceptance: 84.50% | Paid: No Topics: Math, Greedy

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).

• Examples
• Constraints
• Approach 1: String Manipulation
• Approach 2: Mathematical (Greedy)
• Approach 3: Brute Force

Examples

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

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

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

Constraints

- 1 <= num <= 10^4
- num consists of only 6 and 9 digits.

Approach 1: String Manipulation

Intuition Convert the number to a string to easily access and modify specific digits. The optimal strategy is to find the first occurrence of ‘6’ (from the left) and change it to ‘9’.

Steps

• Convert the integer num to a string.
• Iterate through the string or use the replace function to change the first ‘6’ to ‘9’.
• Convert the modified string back to an integer and return it.

class Solution:
    def maximum69Number (self, num: int) -> int:
        s = str(num)
        s = s.replace('6', '9', 1)
        return int(s)

Complexity

• Time: O(log n) - Converting to string and iterating takes time proportional to the number of digits.
• Space: O(log n) - To store the string representation of the number.
• Notes: Simple and readable, but uses extra space for the string.

Approach 2: Mathematical (Greedy)

Intuition To maximize the number, we must change the leftmost ‘6’ to a ‘9’. This is because a digit in a higher place value contributes more to the total number than a digit in a lower place value. We can scan the digits from right to left to find the highest place value where a 6 exists, then add 3 * place_value to the number.

Steps

• Initialize a variable to keep track of the place value of the first ‘6’ found from the left (or highest power of 10).
• Iterate through the number by dividing by 10. If the last digit is 6, record the current place value.
• After the loop, if a 6 was found, add 3 * place_value to the original number.
• Return the result.

class Solution:
    def maximum69Number (self, num: int) -> int:
        i = 0
        first_six = -1
        temp = num
        while temp > 0:
            if temp % 10 == 6:
                first_six = i
            temp //= 10
            i += 1
        if first_six != -1:
            num += 3 * (10 ** first_six)
        return num

Complexity

• Time: O(log n) - We iterate through the digits of the number.
• Space: O(1) - We only use a few integer variables.
• Notes: Most optimal in terms of space complexity.

Approach 3: Brute Force

Intuition Generate all possible numbers by flipping each digit (6 to 9 or 9 to 6) one by one, and keep track of the maximum value encountered.

Steps

• Convert the number to a list of characters (or digits).
• Iterate through each digit.
• Flip the digit (if 6 make it 9, if 9 make it 6).
• Convert the list back to a number and update the maximum value found so far.
• Revert the change to try the next position.
• Return the maximum value.

class Solution:
    def maximum69Number (self, num: int) -> int:
        s = list(str(num))
        max_val = num
        for i in range(len(s)):
            original = s[i]
            if original == '6':
                s[i] = '9'
            else:
                s[i] = '6'
            max_val = max(max_val, int(''.join(s)))
            s[i] = original
        return max_val

Complexity

• Time: O((log n)²) - We iterate through digits (log n) and for each, we join/parse (log n).
• Space: O(log n) - To store the list of digits.
• Notes: Less efficient than the greedy approach but conceptually straightforward.