Skip to main content
CodePeet

Maximum 69 Number

Try it yourself
EasyProblemExternal link

Description

You are given a positive integer num whose digits are all 6s and 9s. You may change at most one digit: a 6 into a 9, or a 9 into a 6.

Return the largest number you can get.

Examples

Example 1

Input: num = 9696

Output: 9996

Explanation: Changing the digits one at a time gives 6696, 9996, 9666 and 9699, and changing nothing keeps 9696. The largest of these is 9996.

Example 2

Input: num = 6

Output: 9

Explanation: The only digit is a 6, and turning it into a 9 gives 9.

Example 3

Input: num = 9999

Output: 9999

Explanation: Every change would turn a 9 into a 6 and make the number smaller, so the best choice is to change nothing.

Constraints

  • 1 ≤ num ≤ 10^4
  • num consists only of the digits 6 and 9.

Editorial

Brute Force

Intuition

Only a few numbers can be reached: num itself, by changing nothing, and one number per digit, with that one digit flipped. A number with d digits gives d + 1 choices, at most 5 here. Build every one of them and keep the largest.

Flipping one digit. It is easiest on the number's text. Turn num into a string, replace the character at position i, and turn the result back into a number. Python strings cannot be changed in place, so the new string is built from three pieces: digits[:i], the flipped digit, and digits[i + 1:]. C++ can change a copy of the string directly, and Java uses a StringBuilder.

Don't forget "at most one". Changing nothing is allowed, and sometimes it is the best choice: for 9999, every change makes the number smaller. That is why best starts at num and not at 0.

Step-by-Step Explanation

We trace Example 1, num = 9696. The top row is the number with one digit flipped and the second row is the original; a flipped digit is green when it became a 9 and orange when it became a 6. The place values are underneath.

Step 1: Start with best = 9696: changing nothing is allowed.

Step 2: Position 0: 9 becomes 6, giving 6696. best stays 9696.

Step 3: Position 1: 6 becomes 9, giving 9996. New best: 9996.

Step 4: Position 2: 9 becomes 6, giving 9666. best stays 9996.

Step 5: Position 3: 6 becomes 9, giving 9699. best stays 9996.

Step 6: All 4 changes are tried. Return 9996.

Brute Force — Try Every One-Digit Change — Example 1, num = 9696: each digit is flipped in turn (top row) against the original (second row), and the largest result is kept.

Algorithm

  1. Let digits be num written as text, and set best = num.
  2. For each position i:
    • Copy digits with the digit at i flipped (6 → 9 or 9 → 6).
    • Turn the copy back into a number, and keep it in best if it is larger.
  3. Return best.

Code

#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    int maximum69Number(int num) {
        string digits = to_string(num);
        int best = num;  // changing nothing is allowed
        for (int i = 0; i < (int)digits.size(); i++) {
            string changed = digits;
            changed[i] = digits[i] == '6' ? '9' : '6';
            best = max(best, stoi(changed));
        }
        return best;
    }
};
class Solution:
    def maximum69Number(self, num: int) -> int:
        digits = str(num)
        best = num  # changing nothing is allowed
        for i in range(len(digits)):
            flipped = '9' if digits[i] == '6' else '6'
            best = max(best, int(digits[:i] + flipped + digits[i + 1:]))
        return best
class Solution {
    public int maximum69Number(int num) {
        String digits = String.valueOf(num);
        int best = num;  // changing nothing is allowed
        for (int i = 0; i < digits.length(); i++) {
            StringBuilder changed = new StringBuilder(digits);
            changed.setCharAt(i, digits.charAt(i) == '6' ? '9' : '6');
            best = Math.max(best, Integer.parseInt(changed.toString()));
        }
        return best;
    }
}

Complexity Analysis

Let d be the number of digits, at most 5 here.

Time Complexity: O(d²). There are d candidates, and building and reading each one takes O(d).

Space Complexity: O(d) for the text of the number and one candidate at a time.

Why This Approach Is Not Efficient

At this size it costs almost nothing: measured in Python, about 0.5 microseconds for num = 6666. What it lacks is a reason. It builds every candidate because it does not know which one will win, and most of them could have been ruled out without being built:

  • A 9 that becomes a 6 always makes the number smaller, so those candidates can never be the answer.
  • Among the 6s, the leftmost always wins, because its place value is the largest.

Knowing both, there is nothing left to search for. The next approach goes straight to the answer, and its work grows only with the number of digits, not with the number of digits times the number of candidates.

Optimal Approach - Turn the Leftmost 6 Into a 9

Intuition

Why the leftmost 6. Changing one digit changes the number by the difference in that digit times its place value. A 6 that becomes a 9 adds 3 × its place: in 9696, the 6 at place 100 adds 300 and the 6 at place 1 adds 3. A 9 that becomes a 6 subtracts 3 × its place, so it never helps. Only one change is allowed, so the best change is the 6 with the largest place value, which is the leftmost 6. If there is no 6 at all, the number is already all 9s and nothing should change.

There is no trade-off to weigh, because a single change touches a single place: the biggest gain is simply the biggest place value holding a 6.

The number 9696 with place values 1000, 100, 10 and 1. Turning the 9 at 1000 into a 6 would subtract 3000, the 6 at 100 into a 9 adds 300, the 9 at 10 into a 6 subtracts 30, and the 6 at 1 into a 9 adds 3. The biggest gain is the leftmost 6: 9696 + 300 = 9996.

Doing it with arithmetic instead of text. The digits of a number can be read without turning it into a string. n % 10 is its last digit, and n // 10 drops that digit (in C++ and Java, n / 10 does the same for whole numbers). Repeating the two reads the digits from right to left, and a place that starts at 1 and is multiplied by 10 each round says what each digit is worth. Remember the place of every 6 you meet. Because the digits arrive right to left, the last place remembered belongs to the leftmost 6. The answer is num + 3 × highest_six, and if no 6 was met, highest_six is 0 and num comes back unchanged.

Reading 9696 from the right: n = 9696 gives last digit 6 at place 1, n = 969 gives 9 at place 10, n = 96 gives 6 at place 100, and n = 9 gives 9 at place 1000. highest_six ends at 100, the place of the leftmost 6, and 9696 + 3 × 100 = 9996.

The same idea with text. Replacing only the first 6 in the number's text does the same job. In Python, str(num).replace('6', '9', 1) replaces just the first 6, and int(...) turns the result back into a number. In C++, to_string(num), then s.find('6') gives the first 6 (if it is not npos, set that character to '9'), and stoi reads it back. In Java, String.valueOf(num), then replaceFirst("6", "9"), then Integer.parseInt. The code below uses the arithmetic version, which never builds the text at all.

Step-by-Step Explanation

We trace Example 1, num = 9696, with each digit's place value underneath. The digit being read is blue; the 6 whose place is currently remembered is green.

Step 1: Start with n = 9696, place = 1 and highest_six = 0.

Step 2: n = 9696: the last digit is 6, worth 1. A 6, so highest_six = 1.

Step 3: n = 969: the last digit is 9, worth 10. A 9; highest_six stays 1.

Step 4: n = 96: the last digit is 6, worth 100. A 6, so highest_six = 100.

Step 5: n = 9: the last digit is 9, worth 1000. A 9; highest_six stays 100.

Step 6: Return 9696 + 3 × 100 = 9996.

Read the Digits From the Right, Keep the Place of the Last 6 — Example 1, num = 9696, with each digit's place value underneath. The digits are read right to left with % 10 and // 10.

Algorithm

  1. Set place = 1, highest_six = 0 and n = num.
  2. While n > 0:
    • If n % 10 == 6, set highest_six = place.
    • Set n = n // 10 and place = place × 10.
  3. Return num + 3 × highest_six.

Keep overwriting. Setting highest_six every time a 6 is met, rather than only the first time, is what makes it the leftmost 6: the digits come right to left, so the first 6 met is the rightmost one. For 9696, stopping at the first 6 would add 3 instead of 300 and return 9699.

Code

class Solution {
public:
    int maximum69Number(int num) {
        int place = 1, highestSix = 0;
        for (int n = num; n > 0; n /= 10, place *= 10)
            if (n % 10 == 6) highestSix = place;  // digits come right to left, so the last 6 seen is the leftmost
        return num + 3 * highestSix;  // a 6 turned into a 9 adds 3 at its place value
    }
};
class Solution:
    def maximum69Number(self, num: int) -> int:
        place, highest_six = 1, 0
        n = num
        while n > 0:
            if n % 10 == 6:
                highest_six = place  # digits come right to left, so the last 6 seen is the leftmost
            n //= 10
            place *= 10
        return num + 3 * highest_six  # a 6 turned into a 9 adds 3 at its place value
class Solution {
    public int maximum69Number(int num) {
        int place = 1, highestSix = 0;
        for (int n = num; n > 0; n /= 10, place *= 10)
            if (n % 10 == 6) highestSix = place;  // digits come right to left, so the last 6 seen is the leftmost
        return num + 3 * highestSix;  // a 6 turned into a 9 adds 3 at its place value
    }
}

Complexity Analysis

Time Complexity: O(d). One round per digit. Measured in Python, about 0.15 microseconds for num = 6666.

Space Complexity: O(1). Three integers; no text is built.