Problem Description

You are given a positive integer num consisting only of the digits 6 and 9. You are allowed to change at most one digit (either from 6 to 9 or from 9 to 6). Your task is to return the maximum number you can obtain by changing at most one digit.

Constraints:

• 1 <= num <= 10^4
• num contains only the digits 6 and 9
• You may only change one digit

Example:
Input: 9669
Output: 9969
Explanation: Changing the first digit from 6 to 9 yields the largest number.

Thought Process

Let's start by thinking about what makes the number as large as possible. Since the number is made up of only 6s and 9s, and we are allowed to change only one digit, the optimal strategy is to change the first 6 (from the left) to a 9. This is because digits on the left have higher place value, so changing them has a bigger impact on the overall number.

Brute-force would try all possible one-digit changes, but that's unnecessary: changing any 9 to 6 would only make the number smaller, so we never want to do that. Instead, we simply scan from left to right and change the first 6 we find to 9.

If there is no 6 in the number, then the number is already the largest possible, and we return it as is.

Solution Approach

• Step 1: Convert the integer num into a string or character array so we can easily access and modify individual digits.
• Step 2: Iterate through the digits from left to right.
• Step 3: When you find the first 6, change it to 9 and stop (since only one change is allowed).
• Step 4: Convert the modified string or character array back to an integer and return it.
• Justification: This approach works because changing the leftmost 6 increases the number by the largest possible amount, due to place value.
• Edge Case: If there is no 6 in the number, simply return the original number.

Example Walkthrough

Let's walk through the example with num = 9669:

1. Convert 9669 to a list of characters: ['9', '6', '6', '9']
2. Start scanning from the left:
   • First digit: '9' (do nothing)
   • Second digit: '6' (this is the first 6, so change it to '9')
3. Now the list is ['9', '9', '6', '9']
4. Convert back to integer: 9969
5. Return 9969 as the answer.

If the input was 9999, scanning from left to right finds no 6, so we return 9999.

Code Implementation

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

class Solution {
public:
    int maximum69Number (int num) {
        string s = to_string(num);
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '6') {
                s[i] = '9';
                break;
            }
        }
        return stoi(s);
    }
};
      

class Solution {
    public int maximum69Number (int num) {
        char[] digits = Integer.toString(num).toCharArray();
        for (int i = 0; i < digits.length; i++) {
            if (digits[i] == '6') {
                digits[i] = '9';
                break;
            }
        }
        return Integer.parseInt(new String(digits));
    }
}
      

var maximum69Number  = function(num) {
    let numArr = num.toString().split('');
    for (let i = 0; i < numArr.length; i++) {
        if (numArr[i] === '6') {
            numArr[i] = '9';
            break;
        }
    }
    return parseInt(numArr.join(''));
};
      

Time and Space Complexity

• Brute-force approach: Try changing each digit one by one and keep track of the largest number. For a number with n digits, this is O(n) time and O(n) space (since we create a new number for each change).
• Optimized approach (our solution):
  • Time Complexity: O(n), where n is the number of digits in num. We scan each digit at most once.
  • Space Complexity: O(n), for storing the string or character array representation of num.
  This is optimal for this problem.

Summary

In summary, to get the maximum number from a number made of 6s and 9s by changing at most one digit, we simply convert the number to a string, change the first 6 to a 9, and return the result. This leverages the place value system for maximum impact and avoids unnecessary computations. The solution is both simple and efficient, making it a great example of how analyzing the problem's constraints can lead to an elegant answer.