A friend of mine works in a data management company and he needs to compulsively records all the backuped data on CD Roms. To this end, he has a huge collection of CD ROMs. He has long given up on trying to label these cassettes with any meaningful names. Now he just numbers them and maintain the description based on number given to CD else where. The numbers go from 1 up and are consecutive.
In order to label the CDs, he uses the digit stickers that come with a bought CD. Each CD comes with one sticker for each digit(0-9).
So, for example, to label the first CD, he uses just the sticker "1" and keeps the rest. To label the second, he uses just the sticker "2" and keeps the rest. To label the tenth, he uses two stickers, one "1" and one "0", and keeps the rest. To label the eleventh, he uses one "1" sticker from the stickers he just got, and one "1" sticker which he had in stock from the previous ten. And so on.
The question is, what is the number of the first CD which he will no longer be able to label in this way (i.e., that will deplete his stock of stickers to the point that he will not be able to form the desired number)? Please give your answer for general B, as well as for B=10. Please supply a proof if posssible.
Links: Mathematical Solution, Coded Solution
The first digit to run out will be the "1"s digit is always the one with the lowest stock. All other digits are inconsequential.
ReplyDeleteHence we need to count the number of digit 1 coming in all the numbers till N until we find the first N for which the number of digits are more than the number itself.
For example the number of 1 till 100 is 10 + 10 =20.
The number of 1 till 1000 are 100(for hundred place) + 100(for tens place) + 100 for ones place total 300.
Similarly no fo1s till 10,000 are 4000. Also the number we are looking for will be between 10^x and 2*10*x. Eg it will be between 10-20 or 100-200, or 1000-2000, or 10000-200000 or so on. By searching through the reduced space we can find the first number to be 199991. There is a mathematical approach for reaching at the solution as well. If you are interested then look at the link. https://docs.google.com/file/d/0B1RemqblO3BZd0NPUllxdjgxTWs/edit?usp=sharing
The problem can be coded as well. I have coded the solution for a general cased where the base can be any thing between 2 to 62. How ever the algorithm is of exponential complexity and finding a solution for Base more than 16 can never complete in resonable time.
Here is the code. Change the Radix for different bases.
https://docs.google.com/file/d/0B1RemqblO3BZTUFlczlNdTB6S28/edit?usp=sharing