A vintage rally car's trip odometer displays its reading as a fixed row of digit wheels, one digit (0-9) per wheel, read left to right, with no leading zero in the original reading. A mechanic can perform a single relabelling: pick one digit value d1 that currently appears somewhere on the odometer, and repaint every wheel that currently shows d1 so it instead shows some chosen digit value d2 (d2 may equal d1, in which case nothing actually changes). All wheels showing d1 are repainted together, in that one relabelling; every other wheel is left untouched.
Starting from the original reading, the mechanic wants to know how far apart the best-case and worst-case relabellings can push the displayed number. Concretely: find the largest number obtainable by one such relabelling, find the smallest number obtainable by one separate, independently chosen relabelling (the maximizing and minimizing relabellings are two unrelated hypothetical scenarios, never applied together), and report the difference between the two. A relabelling is allowed to leave the leftmost wheel showing 0; the row of wheels is still read as the corresponding integer, so a leading 0 simply drops out of the value (wheels showing 0, 8, 9 are read as the number 89).
A single line containing one integer N, written as a string of decimal digits with no leading zero.
Print a single integer: the maximum value achievable by one relabelling minus the minimum value achievable by one (independent) relabelling.
Example 1
Input
11891
Expected
99009
Explanation
Digits are 1,1,8,9,1. To maximize, remap every 1 to 9: the wheels become 9,9,8,9,9, i.e. 99899. To minimize, remap every 1 (the leftmost digit) to 0: the wheels become 0,0,8,9,0, i.e. 00890 which reads as 890. The difference is 99899 - 890 = 99009.
Example 2
Input
90
Expected
99
Explanation
Digits are 9,0. The leftmost digit is already 9, so to maximize we remap the next non-9 digit, 0, to 9: the wheels become 9,9, i.e. 99. To minimize, remap the leftmost digit, 9, to 0: the wheels become 0,0, i.e. 0. The difference is 99 - 0 = 99.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →