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 <= 104num consists of only 6 and 9 digits.The key observation in #1323 Maximum 69 Number is that the number only contains digits 6 and 9, and you are allowed to change at most one digit. To maximize the value, you should prioritize modifying the digit that has the greatest positional impact.
A greedy strategy works best here. Since digits on the left contribute more to the final number, you scan the number from left to right and look for the first occurrence of 6. Changing this digit to 9 yields the maximum possible increase. If the number already consists entirely of 9s, no change is required.
This approach can be implemented by converting the number to a string or by extracting digits mathematically. Because you only scan the digits once, the algorithm is highly efficient with linear time relative to the number of digits and minimal extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy scan to flip first 6 | O(d) | O(1) |
Coding Interviews
Use these hints if you're stuck. Try solving on your own first.
Convert the number in an array of its digits.
Brute force on every digit to get the maximum number.
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.
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(n) for storing the string representation of num.
1#include <stdio.h>
2#include <string.h>
3
4int maximum69Number(int num) {
5 char numStr[5];
6 sprintf(numStr, "%d", num); // Convert integer to string
7 for (int i = 0; numStr[i] != '\0'; ++i) {
8 if (numStr[i] == '6') {
9 numStr[i] = '9';
10 break;
11 }
12 }
13 return atoi(numStr); // Convert string back to integer
14}
15
16int main() {
17 int num = 9669;
18 printf("%d", maximum69Number(num));
19 return 0;
20}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.
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.
Time Complexity: O(1), as we have at most 4 digits to check.
Space Complexity: O(1), using constant space for computations.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar greedy digit-manipulation questions can appear in technical interviews. It tests understanding of greedy decision-making and basic number handling.
The optimal approach uses a greedy strategy. Scan the digits from left to right and change the first occurrence of 6 to 9, since earlier digits contribute more to the overall value of the number.
A greedy method works because flipping the leftmost 6 produces the largest possible increase in the number. Any change to a later digit would result in a smaller improvement.
Most implementations convert the number into a string or array of digits for easy modification. However, it can also be solved using basic math operations without additional data structures.
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'.