Leetcode – Maximum 69 Number Solution

Spread the love

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.

Problem Statement

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).

Constraints:

  • The given num is a positive integer.
  • num will only contain the digits 6 and 9.

Example:

Input: num = 9669
Output: 9969
Explanation: Changing the first digit results in 9969 which is the largest possible number with the given constraint.

Approaches

Brute-Force Approach

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)

Optimized Approach

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.

Edge Cases

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.

Conclusion

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.

Leave a Reply