You get a positive integer made only of the digits 6 and 9. You may change at most one digit (6 to 9 or 9 to 6). Return the largest number you can get. For 9669 the answer is 9969.
def maximum69_number(num):
return int(str(num).replace("6", "9", 1))
Turning a 9 into a 6 only makes the number smaller, so the only useful move is turning a 6 into a 9. The leftmost digit has the biggest place value, so flip the first 6 you see. If there is no 6, the number is already maximal.
def maximum69_number(num):
pos, first6, n = 0, -1, num
while n:
if n % 10 == 6:
first6 = pos # keeps overwriting, so ends at the highest 6
n //= 10
pos += 1
return num if first6 < 0 else num + 3 * 10 ** first6
Changing a 6 to a 9 at position p adds exactly 3 * 10^p. Interviewers sometimes ask for this version to see whether you can reason about place value without string conversion.
Say it as an exchange argument: any solution that flips a lower 6 instead of the highest one gains at most 3 * 10^(p-1), which is always less than 3 * 10^p. One sentence like that turns "I just know it" into a proof.
If you want a second pair of eyes while rehearsing greedy proofs, linkjob.ai offers an AI interview copilot. (Disclosure: I work on Linkjob AI.)
Further reading: Linkjob AI resource directory