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.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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(n) for storing the string representation of num.
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'.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1), as we have at most 4 digits to check.
Space Complexity: O(1), using constant space for computations.
| 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. |
Maximum 69 Number (Leetcode 1323) • Coding Interviews • 1,473 views views
Watch 9 more video solutions →Practice Maximum 69 Number with our built-in code editor and test cases.
Practice on FleetCode