Maximum 69 Number - Solution & Explanation
Problem Statement
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 <= 104numconsists of only6and9digits.
Approach Overview
Problem Overview: You are given a positive integer composed only of digits 6 and 9. You may change at most one digit (turn a 6 into a 9 or vice versa). The goal is to produce the maximum possible number after the change.
Approach 1: Greedy Replacement (O(n) time, O(n) space)
This problem fits naturally into a greedy strategy. The most significant digit contributes the most to the final value, so you want to convert the leftmost 6 into 9. Convert the number into a string or digit array, iterate from left to right, and replace the first occurrence of 6 with 9. Once this replacement is made, stop the scan because changing any later digit would produce a smaller improvement.
The key insight: flipping the earliest 6 maximizes the place-value increase. For example, changing the first digit of 6999 gives a much larger gain than modifying a later digit. After replacement, convert the string back to an integer. The iteration runs once over the digits, giving O(n) time where n is the number of digits, and O(n) space if a string representation is used.
This approach is simple, readable, and commonly used in interview solutions. It directly reflects the greedy principle of maximizing gain at the highest place value.
Approach 2: Mathematical Transformation (O(n) time, O(1) space)
A purely numerical solution avoids string conversion and operates directly on digits using basic math. Start from the most significant digit by computing powers of ten relative to the number's length. Extract digits using division and modulo operations.
While scanning digits from left to right, detect the first 6. Once found, add 3 × place_value to the number. This works because converting 6 to 9 increases the digit by exactly 3. For example, if the 6 appears in the hundreds place, adding 3 × 100 transforms it to 9. No additional memory structure is needed.
This technique keeps the algorithm strictly numeric while maintaining the same O(n) digit traversal. Space complexity stays O(1) because only a few variables are used. The approach relies on understanding positional values and arithmetic manipulation of digits.
Recommended for interviews: The greedy replacement approach is usually expected. It clearly demonstrates reasoning about digit significance and is easy to implement under time pressure. The mathematical version shows deeper comfort with number manipulation and can impress interviewers, but readability matters more for quick coding rounds involving greedy and math problems.
Approach 1: Approach 1: Greedy Replacement
This approach uses a simple greedy algorithm to find the first occurrence of the digit '6' and replaces it with '9'. This ensures that the number is maximized by making a change that increases the most significant portion of the number.
The function maximum69Number converts the given number to a string, checks each character, and replaces the first '6' with a '9'. Once done, it converts the string back to an integer and returns it.
Complexity
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(n) for storing the string representation of num.
Approach 2: Approach 2: Mathematical Transformation
This approach works directly with the number without converting it to a string. We find the first '6' from the leftmost side by using basic mathematical operations (division and modulo). We can calculate the position and change the digit using arithmetic transformations to make this efficient.
This solution considers each digit by dividing the number with powers of 10. If a '6' is detected at a position, 3 times that power of 10 is added to change the digit to '9'.
Complexity
Time Complexity: O(1), as we have at most 4 digits to check.
Space Complexity: O(1), using constant space for computations.
Approach 3: Greedy
We convert the number to a string, then traverse the string from left to right to find the first occurrence of 6, replace it with 9, and then return the integer corresponding to the converted string.
Time complexity O(log num), space complexity O(log num). Where num is the given integer.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Replacement | Time Complexity: O(n), where n is the number of digits in Space Complexity: O(n) for storing the string representation of |
| Approach 2: Mathematical Transformation | Time Complexity: O(1), as we have at most 4 digits to check. Space Complexity: O(1), using constant space for computations. |
| Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Replacement | O(n) | O(n) | Most common solution. Easy to implement by scanning digits and replacing the first 6. |
| Mathematical Transformation | O(n) | O(1) | When avoiding string conversion or demonstrating digit manipulation using arithmetic. |
Video Solution
Leetcode 1323. Maximum 69 Number • Algorithms Casts • 984 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum 69 Number easy or hard?
Maximum 69 Number Python/Java solution
How to solve Maximum 69 Number in O(n)?
What is the best approach for Maximum 69 Number?
Is Maximum 69 Number asked at Google/Amazon/Meta?
What data structure is used in Maximum 69 Number?
What is the time complexity of Maximum 69 Number?
Ready to solve this problem?
Practice Maximum 69 Number with our built-in code editor and test cases.
Practice on FleetCode