1323. Maximum 69 Number
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 77.9%
Problem Breakdown
The problem requires transforming a given positive integer num, which consists only of digits 6 and 9, into the largest possible number by changing at most one digit (changing a 6 to a 9 or vice versa). The input is a single integer, and the output should be the modified integer that represents the maximum possible value after making at most one change.
Inputs:
- A positive integer
numwith digits only being 6 or 9.
Outputs:
- An integer which is the largest possible number obtainable by changing at most one digit in
num.
Implicit Constraints/Edge Cases:
- If
numconsists entirely of 9s, no change will increase its value. - The input size is limited to four digits (1 <= num <= 10^4), so brute-force approaches are feasible but not optimal.
Intuition
A brute-force approach would involve generating all possible numbers by changing each digit from 6 to 9 and then selecting the maximum. However, this approach is inefficient with a time complexity of O(n) where n is the number of digits in num.
The key insight is that changing the first occurrence of the digit ‘6’ to ‘9’ will yield the largest possible number because it maximizes the impact on the overall value of the number. This approach leverages the positional value of digits and ensures that we achieve the maximum increase with a single change.
Approach
- Convert the integer
numto a string to easily manipulate individual digits. - Iterate through each character in the string representation of
num. - Locate the first occurrence of the digit ‘6’.
- Replace this ‘6’ with ‘9’ and convert the modified string back to an integer.
- Return the resulting integer as it represents the maximum possible number after one change.
Complexity Analysis
- Time Complexity: O(n), where n is the number of digits in
num. This is because we iterate through each digit once to find the first ‘6’. - Space Complexity: O(1) for the additional space used, as we only store a few variables regardless of the input size.
Solution
def maximum69Number(num):
# Convert the number to a string to manipulate individual digits
num_str = str(num)
# Find the first occurrence of '6' and replace it with '9'
max_num_str = num_str.replace('6', '9', 1)
# Convert the modified string back to an integer and return it
return int(max_num_str)
# Example usage:
print(maximum69Number(9669)) # Output: 9969
print(maximum69Number(9996)) # Output: 9999
print(maximum69Number(9999)) # Output: 9999
Edge Cases Handled
- All digits are ‘9’: The function correctly returns the original number since no change can increase its value.
- Single digit input: If
numis a single digit, the function will return it unchanged if it’s ‘9’ or change it to ‘9’ if it’s ‘6’. - Multiple ‘6’s in the number: The function only changes the first occurrence of ‘6’, ensuring the maximum possible increase.