Counting digit occurrences

问题:

This problem is really confusing me; we're given two integers A, B, we want to count occurrences of digits in the range [A, B]. I though that if we could count the number of digit occurrences in the range [0, A] and [0, B], then the rest is trivial. So how can I count digit occurrences in a range [0, x]? This isn't homework, this is actually a problem from SPOJ. The naive approach won't work, as A and B can be as large as 10 ^ 9. Here are some examples:

Input:

1 10

Output:

1 2 1 1 1 1 1 1 1 1

Input:

44 497

Output:

85 185 185 185 190 96 96 96 95 93

回答1:

I would try the brute force approach first to get something working. Look at each number, iterate through each character in the string representation of that number, etc.

However, there is an easier way.

• In the interval [0,9], 3 appears 1 time
• In the interval [0,99], 3 appears 10 times in the first digit and 10 times in the second digit
• In the interval [0,999], 3 appears 100 times in the first digit, 100 times in the second digit and 100 times in the third digit.

You can generalize this and with a bit of effort come up with a formula for how many of a certain digit (0 being a possible special case) will appear in a certain range. You don't need to actually go through each number.

回答2:

Wolfram Alpha is your friend (at least upon some number near 21 * 10^4):

Input:

44 497

Output:

85 185 185 185 190 96 96 96 95 93 

Try Me

Result:

{85, 185, 185, 185, 188, 96, 96, 96, 95, 93}

回答3:

With problems of this kind, it's often useful to start with a slow-and-ugly implementation before working out how to do it properly and fast. You might learn something about the structure of the problem, and you can use the slow implementation to test the correctness of the fast one.

In Python, for example, you might write the slow version like this (it's not necessarily the best way to do it, but it's among the shortest...)

>>> A, B = 1, 100
>>> from collections import Counter
>>> Counter(''.join(map(str, range(A, B + 1))))
Counter({'1': 21, '3': 20, '2': 20, '5': 20, '4': 20,
         '7': 20, '6': 20, '9': 20, '8': 20, '0': 11})