algorithm - An interview puzzle: A Broken Calculator -

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