Maximum 69 Number: Greedy Digit Replacement
You are given a positive integer num consisting only of digits 6 and 9. You can change at most one digit (6 becomes 9 or 9 becomes 6) to produce the maximum possible number. Return the maximum number you can get.
This is LeetCode 1323: Maximum 69 Number.
Why this problem matters
Maximum 69 Number is a clean introduction to greedy reasoning about digit significance. The constraints are minimal (only two possible digits, one allowed change), which strips the problem down to a single core idea: higher place values matter more. This same principle shows up in harder problems involving digit manipulation, number construction, and optimization under constraints.
The key insight
Think about what each possible change does to the number:
- Changing a 6 to 9 increases the number (you are adding value).
- Changing a 9 to 6 decreases the number (you are removing value).
Since you want the maximum, you should never change a 9 to 6. You should only change a 6 to 9.
Now, which 6 should you change? The leftmost one. Digits further to the left have higher place values. If the number is 9669, changing the 6 at index 1 (the hundreds place) adds 300, while changing the 6 at index 2 (the tens place) would only add 30. The leftmost 6 always gives the largest increase.
When optimizing digit-based numbers, always think about place value. The leftmost digits have exponentially more weight than the rightmost ones. A greedy left-to-right scan is often the right approach.
The solution
def maximum69Number(num):
s = str(num)
for i, ch in enumerate(s):
if ch == '6':
return int(s[:i] + '9' + s[i+1:])
return num
Convert the number to a string, then scan left to right. The moment you find a '6', replace it with '9' and return the new number as an integer. If there is no '6' at all, the number is already all 9s and cannot be made larger, so return it unchanged.
You can also solve this without string conversion by using math. Divide by decreasing powers of 10 to find the first 6 digit, then add the appropriate power of 10 times 3. The string approach is simpler and equally efficient given the small input size (at most 4 digits).
Visual walkthrough
Step 1: Scan digits from left to right
We want to find the leftmost 6 because it occupies the highest place value. Changing it to 9 gives the largest possible increase.
Step 2: Find the first 6
At index 1, we find the first digit that is 6. This is the digit we want to change.
Step 3: Change the first 6 to 9
Replacing 6 with 9 at the hundreds place adds 300 to the number. This is the maximum possible gain from a single digit change.
Step 4: Return the result
The maximum number achievable from 9669 by changing at most one digit is 9969.
The algorithm stops as soon as it finds the first 6 and makes the change. There is no need to continue scanning because only one change is allowed and the leftmost 6 is always the optimal choice.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Greedy (string conversion) | O(n) | O(n) |
Here n is the number of digits. You scan through the string once (O(n) time) and create a new string for the result (O(n) space). For this specific problem, n is at most 4, so both are effectively O(1). But the algorithm generalizes to numbers of any length.
The building blocks
1. Greedy left-to-right scan
The pattern of processing elements from left to right and making a locally optimal decision at the first opportunity:
for i, element in enumerate(sequence):
if condition(element):
apply_change(i)
break
This same pattern appears whenever the leftmost occurrence is the most impactful. In problems like "remove K digits to make the smallest number," you scan left to right looking for the first digit that is larger than its neighbor. The skeleton is the same: scan, find the best spot, act once.
2. Digit significance and place value
Understanding that digits at higher positions have exponentially more weight is the foundation for many number manipulation problems. When you need to maximize a number, prioritize changes to the leftmost digits. When you need to minimize, also start from the left. The place value system means that any change at position i outweighs all possible changes at positions to the right of i combined.
Edge cases
Before submitting, make sure your solution handles these:
- All 9s (
9999): No 6 exists, so return the number unchanged. The loop finishes without finding a '6'. - All 6s (
6666): The first digit is already a 6. Change it to 9, returning9666. - Single digit 6 (
6): Change it to9. - Single digit 9 (
9): Already maximum, return9. - 6 at the end (
9996): The only 6 is in the ones place. Change it to get9999. - Multiple 6s (
6669): Change only the first one to get9669. You are allowed at most one change.
The greedy solution handles all of these without special-case logic.
From understanding to recall
This problem is short and the solution is simple. But "simple" does not mean "memorable." In an interview, the pressure is on and you need to produce clean code without hesitation. Can you recall that the answer is always "find leftmost 6, change to 9, done"? Can you write the string-slicing logic correctly on the first try?
The building block here, greedy left-to-right scan with early termination, is shared with dozens of other problems. Drilling it with spaced repetition means you recognize the pattern instantly and write the code from muscle memory. You spend your interview time on harder problems instead of second-guessing a simple greedy choice.
Related posts
- Lemonade Change - Another greedy problem where a simple priority rule is provably optimal
- Gas Station - Greedy optimization with a single pass and running totals
- Jump Game - Greedy forward scanning to determine reachability
CodeBricks breaks the maximum 69 number problem into its greedy scan and digit significance building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy digit manipulation question shows up in your interview, you do not think about it. You just write it.