Geek Answers Handbook

Number counting

This problem really bothers me; we are given two integers A , B , we want to count the numbers of digits in the range [A, B] . However, if we could count the number of digits in the range [0, A] and [0, B] , then the rest is trivial. So how can I count numbers in the range [0, x] ? This is not homework, this is actually a SPOJ problem. The naive approach will not work, since A and B can reach 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 96 95 93

+4
source share
3 answers

At first, I would try to apply brute force to work something. Look at each number, swipe over each character in a lowercase 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 little effort come up with a formula for how many specific figures (0 - a possible special case) will appear in a certain range. You do not really need to go through each number.

+8
source

Wolfram Alpha is your friend (at least next to 21 * 10 ^ 4):

Input: 44 497 Output: 85 185 185 185 190 96 96 96 95 93

To try

Result:

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

+1
source

With such problems, it is often useful to start with a slow and ugly implementation, before starting to develop how to do it right and quickly. You can learn something about the structure of the problem, and you can use the slow implementation to verify the correctness of the fast.

In Python, for example, you can write a slow version like this (this is not necessarily the best way to do this, but it is one of 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})
-1
source

More articles:


All Articles