Maximum 69 Number

EASY

Description

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

Checkout 3 different approaches to solve Maximum 69 Number. Click on different approaches to view the approach and algorithm in detail.

Brute Force by Generating All Possibilities

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.

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 Analysis

Time Complexity: 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 Complexity: O(d), where `d` is the number of digits. This space is used to store the string representation and the character array.

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Maximum 69 Number. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Maximum 69 Number

Patterns:

MathGreedy

Companies:

Hudson River Trading |