[title description]

Count the number of k 's between 0 and n. k can be 0-9.

Calculation number k in 0 to the number of occurrences of n, k can be a value of 0 ~ 9,

[title link]

http://www.lintcode.com/en/problem/digit-counts/

[title]

Method one: Brute Force, 0 to n number is in the past, each one of the biggest problems is the efficiency, when n is very large, it needs a long running time,

Method 2: when one number is less than I, then the bit in the number of times I to: higher digits x current digits; When one number is equal to the I, so the bit in the number of times I to: higher digits x number + number + 1 low current; When one number is greater than I, then the bit in the number of times I to: (higher digits x + 1) current digits

Suppose that a 5 digit N=abcde, we now consider one hundred appear on the 2 times, that is, from 0 to the number of abcde, how many on one hundred - bit number is 2, after analysis it, you can use the same method to calculate the bits, 10, one thousand, ten thousand and so on each place 2 times,

When one hundred c to 0, for example, 0 to 12013 in 12013 which will be displayed in a one hundred - bit number? We grew up a number of 200 ~ 299, 1200 ~ 1299, 2200 ~ 2299,... , 11200 ~ 11299, namely fixed low of 200 ~ 299 in 3 patients, and then high in turn from 0 to 11, a total of 12, following 12200 ~ 12299 has more than 12013, so no longer downwards, so, when one hundred to 0, one hundred appear 2 times only up to a greater degree, current digits equals higher digits (12) x (100)=1200,

When one hundred c for 1, 12113, for example the above analysis, and is the same as the above situation, is only the largest of 11200 ~ 11299, so the number of one hundred in 2 is also 1200,

The above two steps together, can get the following conclusion:

When one number is less than 2, then 2 times for the bit: higher digits x current digits

When one hundred c for 2, 12213, for example, then, we have 200 ~ 299, 1200 ~ 1299, 2200 ~ 2299,... 1200, 11200 ~ 11299 the number of their one hundred to 2, but at the same time, some 12200 ~ 12213, a total of 14 (low number + 1), so, when a one hundred - bit number is 2, one hundred in 2 times is affected by high or low influence, the conclusion is as follows:

When one number is equal to 2, then 2 times for the bit: higher digits x number + number + 1 low current

When one hundred c is greater than 2, 12313, for example, then fixed low of 200 ~ 299 in 3 patients, high, in turn, can be from 0 to 12, this time also includes 12200 ~ 12299, what also not low, so 2 number is: (higher number + 1) x current figures, the conclusion is as follows:

When one number is greater than 2, then the bit appear 2 times to: (higher digits x + 1) current digits

[the reference answer]

http://www.jiuzhang.com/solutions/digit-counts/