One of the problems on Leetcode that serves as a great warm-up for beginners and intermediates alike is the “Maximum 69 Number” problem.
In this article, we are going to dissect the problem thoroughly, exploring multiple ways to approach it, including the brute-force approach and the optimized approach.
The problem is straightforward and goes as follows:
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).
- The given
numis a positive integer.
numwill only contain the digits 6 and 9.
Input: num = 9669 Output: 9969 Explanation: Changing the first digit results in 9969 which is the largest possible number with the given constraint.
In this approach, we convert the number to a list of its digits and then loop through the list, changing one digit at a time to see which configuration gives us the maximum number.
def maximum69Number(num): num_str = str(num) max_num = num for i in range(len(num_str)): # Create a list from the number's digits num_list = list(num_str) # Change the current digit if num_list[i] == '6': num_list[i] = '9' else: num_list[i] = '6' # Convert the list back to a number new_num = int("".join(num_list)) # Update max_num if a larger number is found max_num = max(max_num, new_num) return max_num
Time Complexity: O(N^2)
Space Complexity: O(N)
In the optimized approach, we only swap the first occurrence of 6 with 9. This ensures that we obtain the maximum number since we are maximizing the place value of the modified digit.
def maximum69Number(num): num_str = str(num) num_list = list(num_str) for i in range(len(num_list)): if num_list[i] == '6': num_list[i] = '9' return int("".join(num_list)) return num
Time Complexity: O(N)
Space Complexity: O(N)
Explanation of the Optimized Approach
In a number made of digits 6 and 9, replacing the leftmost 6 with a 9 will always generate the largest possible number under the given constraints. This is because digits towards the left have higher place value in decimal numbers.
For example, consider the number 9669. The thousands place is more valuable than the hundreds, tens, or ones place. So replacing the leftmost 6 will make the number as large as possible.
What happens if the number consists solely of the digit 9? Well, in that case, changing a 9 to a 6 would make the number smaller. The function, as designed, will return the input number itself.
The “Maximum 69 Number” problem on Leetcode is an excellent question for beginners. It tests your basic understanding of string and list manipulation in Python, as well as your understanding of number properties. While the problem may be solved easily with a brute-force approach, understanding why the optimized solution works the way it does adds another layer of depth to your problem-solving skills.