Maximum 69 Number
Problem
You are given a positive integer num whose decimal digits are only 6s and 9s. You may change at most one digit — turn a 6 into a 9 or a 9 into a 6. Return the largest number you can end up with.
num = 96699969def maximum_69_number(num):
digits = list(str(num))
for i, d in enumerate(digits):
if d == '6':
digits[i] = '9' # flip the leftmost 6
break
return int("".join(digits))function maximum69Number(num) {
const digits = String(num).split("");
for (let i = 0; i < digits.length; i++) {
if (digits[i] === "6") {
digits[i] = "9"; // flip the leftmost 6
break;
}
}
return Number(digits.join(""));
}int maximum69Number(int num) {
char[] digits = String.valueOf(num).toCharArray();
for (int i = 0; i < digits.length; i++) {
if (digits[i] == '6') {
digits[i] = '9'; // flip the leftmost 6
break;
}
}
return Integer.parseInt(new String(digits));
}int maximum69Number(int num) {
string digits = to_string(num);
for (int i = 0; i < (int)digits.size(); i++) {
if (digits[i] == '6') {
digits[i] = '9'; // flip the leftmost 6
break;
}
}
return stoi(digits);
}Explanation
Only two kinds of change exist: a 6 can become a 9 (the digit gains 3) or a 9 can become a 6 (the digit loses 3). Since we want the largest result, turning a 9 down is never useful — the only sensible move is to turn a single 6 into a 9, or do nothing if there is no 6.
Which 6 should we flip? The one in the highest place value, i.e. the leftmost 6. Flipping the 6 at place 10^k adds exactly 3·10^k to the number, and a bigger k always beats a smaller one: the two candidate results agree on every digit before the leftmost 6 and differ right there, so the number that has a 9 in that position is strictly larger no matter what the rest looks like. That single comparison is the whole greedy proof.
The algorithm is a single left-to-right scan: walk the digits, and at the first 6 replace it with a 9 and stop. Everything to the right is left untouched — changing anything there could only add a smaller power of ten (or shrink the number).
Default example num = 9669: index 0 is a 9, so we keep scanning; index 1 is the first 6, so we flip it and break, giving 9969. Compare the alternatives — flipping the second 6 yields 9699, and flipping a 9 yields 6669 or 9666 — all smaller.
If the number is all 9s (say 9999), the scan finds no 6 and the number is returned unchanged: it is already as large as one flip can make it.
The scan touches each of the d digits at most once, so the time is O(d), and the digit buffer uses O(d) space. On LeetCode num ≤ 10⁴, so d ≤ 4 and the whole thing is effectively constant time.