algorithm - An interview puzzle: A Broken Calculator -
time limit : 2sec / stack limit : 256mb / memory limit : 256mb
problem dave's calculator broken. halts when presented more k different digits.
dave wants input integer a, if inputs number correctly calculator might halt. instead, inputs closest integer won't halt calculator.
output difference between dave's input , integer a.
input
the input given in next format standard input.
a k on first line, given integer a(1≦a≦10^15), integer dave wants input, followed space , k(1≦k≦10), number of different digits calculator can recognize.
output
output minimum difference between dave's input , integer in 1 line. create sure insert line break @ end of output.
input illustration 1
1234 2 output illustration 1
12 in case dave can utilize 2 different digits. input closest integer 1222, difference 12.
input illustration 2
7328495 10 output illustration 2
0 in case dave's calculator not broken @ all. can input given integer is.
input illustration 3
800000 1 output illustration 3
22223 dave can utilize 1 digit, 777777 closest integer.
input illustration 4
262004 2 output illustration 4
218 the closest integer 262222.
i have solved problem brute forcefulness solution...
i seek possible situation in 1<= < or < <= 10^15.
i'll 2 solutions composed k different digits, , find min difference between , solutions.
it's straightforward solution.
when larger, execution exceed threshold of 2 sec.
is there smart , efficient way solve it?
the first part is: take k digits (out of 10 possible) used in result bit math (binomial coefficient) it´s easy calculate number of different digit combinations possible given k. there 252 possibilities take (252 if k=5, else not many).
if not clear i´m saying: k=2, there 01,02,03,...09,12,13,...,19,23,24,...,89 no eg. 11 because it´s 1 k=2 allows 2 different digits. , no eg. 90 because it´s same 09, 91=19 etc. count of these possible combinations 252 k=5, , won´t larger.
finding of (up to) 252 possibilities current k , iterating on them in loop shouldn´t hard.
for each of possibilities following: {
within loop, have a, k, , current choosen valid digits solution (latter differs in each iteration of loop, of course) lets take a=12899, k=3, digits 123 example. search first digit of (from left right) not allowed. in example, 12899, because 1 , 2 left of allowed.
replace (8) next-lower allowed digit (2) if there one , replace right of highest possible digit (3 too). 12899=>12399=>12333 save result 12333 somewhere in array etc. if there no next-lower possible digit, nil (nothing goes array)
(a proper add-on carry introduce new digit left of changed one, ie. invalid. solution new digit found when loop comes digit)
then same thing 1 time again in other direction: replace found digit next-higher possible one , right lowest. goes in array too, of course of study if there next-higher possible digit. in case of 12899, higher replacement 8 9, 9 not possible (only 123).
}
after whole loop has finished (and every iteration has produced 2 new array entries), have 502 possible solutions problem. thing left check soltion best (ie. calculate difference every entry , take solution minimal difference)
algorithm
