Maximum 69 Number

Easy

#1230Time: O(d^2), where `d` is the number of digits in `num`. The loop runs `d` times. Inside the loop, converting the string to a character array, creating a new string, and parsing it to an integer each take O(d) time.Space: O(d), where `d` is the number of digits. This space is used to store the string representation and the character array.1 company

Patterns

Math Greedy

Companies

Hudson River Trading

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible number that can be formed by changing a single digit of the input number. We then find the maximum among all the generated numbers, including the original number.

Algorithm

1. Convert the input integer num to its string representation, s.
1. Initialize a variable maxNum with the value of num.
1. Iterate through the string s from the first character to the last.
1. For each character, create a temporary character array from s.
1. If the character at the current index i is '6':
1. Change the character at index i in the temporary array to '9'.
1. Convert the modified character array back to an integer, newNum.
1. Update maxNum to be the maximum of maxNum and newNum.
1. After the loop finishes, return maxNum.

Walkthrough

This method exhaustively checks all possibilities. We convert the number to a character array and iterate through each position. If the digit at the current position is '6', we change it to '9', convert the result back to an integer, and compare it with the maximum number found so far. The initial maximum is the input number itself. This method is guaranteed to work but is inefficient because it continues to check possibilities even after the optimal one (the first '6') has been found.

1class Solution {2    public int maximum69Number (int num) {3        String s = Integer.toString(num);4        int maxNum = num;5        for (int i = 0; i < s.length(); i++) {6            char[] chars = s.toCharArray();7            if (chars[i] == '6') {8                chars[i] = '9';9                maxNum = Math.max(maxNum, Integer.parseInt(new String(chars)));10            }11        }12        return maxNum;13    }14}

Complexity

Time

O(d^2), where `d` is the number of digits in `num`. The loop runs `d` times. Inside the loop, converting the string to a character array, creating a new string, and parsing it to an integer each take O(d) time.

Space

O(d), where `d` is the number of digits. This space is used to store the string representation and the character array.

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to find the correct answer by checking all relevant possibilities.

Cons

Inefficient due to repeated conversions between string and integer inside a loop.
Performs more work than necessary, as the optimal change is always at the first '6'.

A more efficient approach is to realize that to maximize the number, we should change the most significant '6' to a '9'. This means we only need to find the first occurrence of '6' from the left and change it. If no '6' exists, the number is already maximized.

Algorithm

1. Convert the input integer num to a character array chars.
1. Iterate through the chars array from left to right (index i from 0 to length-1).
1. If the character at the current index i is '6':
1. Change this character to '9'.
1. Convert the modified character array back to a string, then parse it to an integer.
1. Return the resulting integer immediately, as we have found the leftmost '6' and made the optimal change.
1. If the loop completes without finding any '6', it means the number consists only of '9's.
1. In this case, return the original num.

Walkthrough

This method leverages string manipulation to find and replace the target digit. First, the integer num is converted to a string or character array. We then iterate from left to right, looking for the first '6'. Once found, we replace it with a '9', convert the modified representation back to an integer, and return it immediately. This is optimal because changing a more significant digit has a greater impact. If the loop finishes without finding a '6', it means the number is already maximized (e.g., 9999), so we return the original number.

1class Solution {2    public int maximum69Number (int num) {3        char[] chars = Integer.toString(num).toCharArray();4        for (int i = 0; i < chars.length; i++) {5            if (chars[i] == '6') {6                chars[i] = '9';7                return Integer.parseInt(new String(chars));8            }9        }10        return num;11    }12}

Alternatively, one could use the built-in replaceFirst method for a more concise solution:

1class Solution {2    public int maximum69Number (int num) {3        return Integer.parseInt(Integer.toString(num).replaceFirst("6", "9"));4    }5}

Complexity

Time

O(d), where `d` is the number of digits in `num`. Converting the number to a string/char array takes O(d). The loop runs at most `d` times. Converting the result back to an integer also takes O(d). The total complexity is linear.

Space

O(d), for storing the string or character array representation of the number, where `d` is the number of digits.

Trade-offs

Pros

Much more efficient than the brute-force approach.
Simple logic: find the first '6' and change it.
Easy to implement using standard string/array functions.

Cons

Requires conversions between integer and string/array types, which can have some overhead.
Uses extra space proportional to the number of digits.

This is the most optimal approach, avoiding any string conversions. It works by mathematically identifying the position of the leftmost '6' and adding the appropriate value to change it to a '9'.

Algorithm

1. Initialize valueToAdd = 0. This will store the value that needs to be added to num to make the change.
1. Initialize powerOf10 = 1. This will represent the current place value (1, 10, 100, ...).
1. Create a temporary copy of the input number, tempNum = num.
1. Loop while tempNum is greater than 0:
1. Get the rightmost digit: digit = tempNum % 10.
1. If digit is 6, we update valueToAdd to 3 * powerOf10. Since we iterate from right to left, this variable will be overwritten by subsequent '6's found at higher place values, ensuring it ultimately holds the value corresponding to the leftmost '6'.
1. Update tempNum to process the next digit: tempNum /= 10.
1. Update the place value: powerOf10 *= 10.
1. After the loop, valueToAdd will be 0 if no '6' was found, or 3 * 10^k if the leftmost '6' was at position k.
1. Return num + valueToAdd.

Walkthrough

The core idea is to find the place value (units, tens, hundreds, etc.) of the leftmost '6'. We can do this by iterating through the digits of the number from right to left. We keep track of the position of the last '6' we encounter during this scan, which corresponds to the leftmost '6' in the number. Changing a '6' to a '9' is equivalent to adding 3 at that digit's place. For example, in 9669, the leftmost '6' is in the hundreds place. Changing it to '9' means adding 3 * 100 = 300, resulting in 9669 + 300 = 9969. If no '6' is found, we add nothing.

1class Solution {2    public int maximum69Number (int num) {3        int tempNum = num;4        int powerOf10 = 1;5        int valueToAdd = 0;6 7        while (tempNum > 0) {8            int digit = tempNum % 10;9            if (digit == 6) {10                // This will be updated for each '6' we find.11                // The last update will correspond to the leftmost '6'.12                valueToAdd = 3 * powerOf10;13            }14            tempNum /= 10;15            powerOf10 *= 10;16        }17 18        return num + valueToAdd;19    }20}

Complexity

Time

O(d), where `d` is the number of digits in `num` (or O(log10(num))). The while loop iterates once for each digit of the number.

Space

O(1). This approach uses only a few extra variables to store state, regardless of the size of the input number.

Trade-offs

Pros

Most efficient in terms of both time and space.
Avoids overhead of string conversions and memory allocations.
Elegant solution using basic arithmetic operations.

Cons

The logic might be slightly less intuitive to grasp at first compared to the straightforward string manipulation approach.

Solutions

Solution

1class Solution {2public3  int maximum69Number(int num) {4    return Integer.valueOf(String.valueOf(num).replaceFirst("6", "9"));5  }6}

1class Solution {2public:3  int maximum69Number(int num) {4    string s = to_string(num);5    for (char &ch : s) {6      if (ch == '6') {7        ch = '9';8        break;9      }10    }11    return stoi(s);12  }13};

1class Solution:2    def maximum69Number(3        self, num: int) -> int: return int(str(num). replace("6", "9", 1))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int maximum69Number(int num) {4    return Integer.valueOf(String.valueOf(num).replaceFirst("6", "9"));5  }6}

1class Solution {2public:3  int maximum69Number(int num) {4    string s = to_string(num);5    for (char &ch : s) {6      if (ch == '6') {7        ch = '9';8        break;9      }10    }11    return stoi(s);12  }13};

1class Solution:2    def maximum69Number(3        self, num: int) -> int: return int(str(num). replace("6", "9", 1))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.