We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum 69 Number

Number: 1448

Difficulty: Easy

Paid? No

Companies: Hudson River Trading

Problem Description

Given a positive integer num, which consists only of the digits 6 and 9, the goal is to obtain the maximum possible number by changing at most one digit. The allowed operation is to switch a 6 to a 9 (or vice versa), but to maximize the overall value, we will change the first occurrence of 6 to 9.

Key Insights

  • The maximum number is achieved by maximizing the leftmost digits.
  • Changing a 6 to a 9 has the most impact when done at the earliest (leftmost) occurrence.
  • Only one digit is allowed to change, so after finding the first 6, we stop.

Space and Time Complexity

Time Complexity: O(n), where n is the number of digits in the number (n is small based on the constraints).
Space Complexity: O(n), since we convert the integer to a string or list for easier manipulation.

Solution

The approach is as follows:

  1. Convert the integer to a string (or an array of characters) so that we can iterate through each digit.
  2. Traverse the string from left to right.
  3. When you encounter the first instance of '6', change it to '9' and break out of the loop, because only one change is allowed.
  4. Convert the modified string back to an integer and return it.

This greedy algorithm ensures that we maximize the numerical value by prioritizing the leftmost possible change. The small size of the input guarantees that the solution is efficient.

Code Solutions

# Convert number to list of characters for easy manipulation.
def maximum69Number(num):
    # Convert integer to list of characters.
    num_str = list(str(num))
    # Loop through each digit.
    for i in range(len(num_str)):
        # If the digit is '6', change it to '9'.
        if num_str[i] == '6':
            num_str[i] = '9'
            break  # Only one change allowed, so break after the first change.
    # Convert the list of characters back to an integer and return.
    return int(''.join(num_str))

# Example usage:
print(maximum69Number(9669))  # Expected output: 9969
← Back to All Questions