algoadvance

You are given a positive integer num consisting only of digits 6 and 9. Your task is to return the maximum number you can obtain by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example:

Clarifying Questions

  1. Q: Can the number num be empty or have any digit other than 6 and 9? A: No, num is a positive integer and will only consist of the digits 6 and 9.

  2. Q: Can we change more than one digit? A: No, we are allowed to change at most one digit.

  3. Q: What is the range of the number of digits in num? A: Since num is a positive integer, it can range from 1 to as many digits as representable in Python.

Strategy

  1. Convert num to a String: Strings are easier to manipulate since we can easily access each character and modify them.
  2. Find the First Occurrence of 6: The optimal strategy is to find the first occurrence of the digit 6 and change it to 9. Changing 9 to 6 would not help in maximizing the number.
  3. Change and Return: Change the first 6 to 9, then convert the string back to an integer and return it.

Code

def maximum69Number(num: int) -> int:
    # Convert number to list of characters to modify
    num_str = list(str(num))
    
    # Traverse through the characters in num_str
    for i in range(len(num_str)):
        if num_str[i] == '6':
            num_str[i] = '9'
            break  # Change only the first 6 and break
    
    # Convert list of characters back to integer
    return int(''.join(num_str))

# Example Usage
print(maximum69Number(9669))  # Output: 9969
print(maximum69Number(9996))  # Output: 9999
print(maximum69Number(6666))  # Output: 9666

Time Complexity

The time complexity of this solution is O(n), where n is the number of digits in num. This is because, in the worst case, we may need to iterate over all the digits to find the first occurrence of 6.

The space complexity is O(n) as well, due to the string conversion which temporarily stores num as a character list.

This solution effectively and efficiently maximizes the given number by altering at most one digit.

Try our interview co-pilot at AlgoAdvance.com