Shulou(Shulou.com)06/03 Report--

[topic description]

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

Calculates the number of occurrences of the number k from 0 to n, which may be a value of 0 to 9.

[topic link]

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

[topic Analysis]

Method 1: Brute Force, the numbers from 0 to n are calculated one by one. The biggest problem is efficiency. When n is very large, it takes a long time to run.

Method 2: when the number of a bit is less than I, then the number of times that the bit appears I is: higher digit x current digit; when the number of a bit is equal to I, then the number of times that bit appears I is: higher digit x current digit + low digit + 1; when the number of a bit is greater than I, then the number of times that bit appears I is: (higher digit + 1) x current digit

Suppose a 5-digit N=abcde, let's now consider the number of times 2 appears on 100, that is, how many of the numbers from 0 to abcde have 2 on 100. After analyzing it, we can use the same method to calculate the number of 2 in each bit, such as ten bits, thousands of bits, ten thousand bits, and so on.

When 100-digit c is 0, for example, which of the 100 digits from 12013 to 12013 will appear 2? We start from a young age, 20000299, 12000012992200002299, … , 11200mm 11299, that is, the fixed low 3 bit is 20000299

Then the high positions range from 0 to 11, a total of 12. Further down 12200-12299 is already greater than 12013, so no further down. Therefore, when the 100 digits are 0, the number of times 2 appears in the 100 digits is only determined by the higher bit, which is equal to the higher digit (12) x the current digit (100) = 1200.

When 100-digit c is 1, say 12113. The analysis is the same as above, and the situation is exactly the same as above. The maximum can only reach 11200 to 11299, so the number of 2 in 100 is also 1200.

Combining the above two steps, the following conclusions can be drawn:

When the number of a bit is less than 2, then the number of times that the bit appears 2 is: higher digit x current digit

When 100-digit c is 2, say 12213. So, we still have 200 million 299, 1200 million 1299, 2200 million 2299,... Of the 1200 numbers of 11200 million 11299, their hundred digits are 2. But at the same time, there are also some 12200 to 12213, a total of 14 (low digit + 1). Therefore, when the 100-digit number is 2, the number of 100-digit occurrence of 2 is affected by both high and low positions. The conclusions are as follows:

When the number of a bit is equal to 2, then the number of times that bit appears 2 is: higher digit x current digit + low digit + 1

When the 100-bit c is greater than 2, say 12313, then the fixed low 3-bit is 2000299, and the high bit can be from 0 to 12. This time 12200-12299 is included, and there is nothing wrong with the low bit. So the number of times 2 occurs is: (higher digit + 1) x current digit. The conclusions are as follows:

When the number of a bit is greater than 2, the number of times that bit appears 2 is: (higher digit + 1) x current digit

[reference answer]

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

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.