GREEDY › PART I

Maximum 69 Number

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionwhy the leftmost change dominates every later one

Changing a 6 to a 9 increases the number, while changing a 9 to a 6 decreases it. Therefore, if a 6 exists, the useful move is to change exactly one 6 into a 9. The remaining choice is which 6 to change.

A digit farther to the left has a larger place value. Changing the leftmost 6 adds 3 times its place value, so it produces a larger increase than changing any 6 after it. If every digit is already 9, no change can improve the number, and the original number is the answer.

Approach

Convert num to a string so you can inspect its digits from left to right without manually calculating place values.
Scan the string from its first character to its last, because the first 6 is the most valuable digit that can be improved.
When you find the first 6, change it to 9 and stop immediately; changing a later digit as well would violate the at-most-one-change rule, and no later 6 can produce a larger increase.
If the scan finds no 6, leave the string unchanged because the number already consists entirely of 9s.
Convert the resulting string back to an integer and return it, since the method must return a numeric value rather than a string.

Complexitythe scan is bounded by the number of digits

MEASURE	BOUND	WHY
Time	O(d)	The scan examines digits only until the first 6 or the end of the string, and converting to and from the string also processes each digit at most once.
Space	O(d) extra	The digit string stores d characters. The returned integer is required output and is excluded from extra space; under the constraint, the worst case has at most 5 digits.

Here d is the number of decimal digits in num; under the given constraint, d is at most 5.

Annotated solutionC++ · greedy left-to-right scan · the version to remember

CPPConvert to digits, replace the first 6, then convert back to an integer.

#include <string>
using namespace std;

class Solution {
public:
    int maximum69Number(int num) {
        string digits = to_string(num);

        for (char& digit : digits) {
            if (digit == '6') {
                digit = '9';
                break;
            }
        }

        return stoi(digits);
    }
};

The break is part of the greedy proof, not merely a small optimisation. The first 6 has the greatest place value among all changeable digits, so it is the only digit worth changing. After it becomes 9, every additional change would either be forbidden or make the result smaller.

The arithmetic alternativeconstant extra space when you do not want a digit string

CPPFind the highest place containing a 6 and add the value of changing it to 9.

#include <string>
using namespace std;

class Solution {
public:
    int maximum69Number(int num) {
        int place = 1;
        while (place <= num / 10) {
            place *= 10;
        }

        while (place > 0) {
            if ((num / place) % 10 == 6) {
                num += 3 * place;
                break;
            }
            place /= 10;
        }

        return num;
    }
};

This version is a genuine space optimisation: it keeps only the current place value instead of allocating a string, so its extra space is O(1). It is less direct because the division and remainder expressions expose place-value arithmetic that the string version hides. Both versions take O(d) time, and the string scan is usually the clearer choice for this problem.

Common mistakestwo wrong code shapes that change the greedy choice

Every part of this item is done.