Scale Engineer

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
MathGreedy
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 <= 104
  • 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.

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

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

Solutions

class Solution {public  int maximum69Number(int num) {    return Integer.valueOf(String.valueOf(num).replaceFirst("6", "9"));  }}

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 →

Next problem