Count the number of occurrences of 0's in integers from 1 to N

Question

How will you efficiently count number of occurrences of 0's in the decimal representation of integers from 1 to N?

e.g. The number of 0's from 1 to 105 is 16. How?

10,20,30,40,50,60,70,80,90,100,101,102,103,104,105    

Count the number of 0's & you will find it 16.

Obviously, a brute force approach won't be appreciated. You have to come up with an approach which doesn't depend on "How many numbers fall between 1 to N". Can we just do by seeing some kind of pattern?

Cannot we extend the logic compiled here to work for this problem?

Answer 1

Updated Answer

My original answer was simple to understand but tricky to code. Here's something that is simpler to code. It's a straight-forward non-recursive solution that works by counting the number of ways zeros can appear in each position.

For example:

x <= 1234. How many numbers are there of the following form?

x = ??0?

There are 12 possibilities for the "hundreds or more" (1,2, ..., 12). Then there must be a zero. Then there are 10 possibilities for the last digit. This gives 12 * 10 = 120 numbers containing a 0 at the third digit.

The solution for the range (1 to 1234) is therefore:

• ?0??: 1 * 100 = 100
• ??0?: 12 * 10 = 120
• ???0: 123
• Total = 343

But an exception is if n contains a zero digit. Consider the following case:

x <= 12034. How many numbers are there of the following form?

x = ??0??

We have 12 ways to pick the "thousands or more". For 1, 2, ... 11 we can choose any two last digits (giving 11 * 100 possibilities). But if we start with 12 we can only choose a number between 00 and 34 for the last two digits. So we get 11 * 100 + 35 possibilities altogether.

---

Here's an implementation of this algorithm (written in Python, but in a way that should be easy to port to C):

def countZeros(n):
    result = 0
    i = 1

    while True:
        b, c = divmod(n, i)
        a, b = divmod(b, 10)

        if a == 0:
            return result

        if b == 0:
            result += (a - 1) * i + c + 1
        else:
            result += a * i

        i *= 10

Answer 2

I would suggest adapting this algorithm from base 2 to base 10:

Number of 1s in the two's complement binary representations of integers in a range

The resulting algorithm is O(log N).

The approach is to write a simple recursive function count(n) that counts the zeroes from 1 to n.

The key observation is that if N ends in 9, e.g.:

123456789

You can put the numbers from 0 to N into 10 equal-sized groups. Group 0 is the numbers ending in 0. Group 1 is the numbers ending in 1. Group 2 is the numbers ending in 2. And so on, all the way through group 9 which is all the numbers ending in 9.

Each group except group 0 contributes count(N/10) zero digits to the total because none of them end in zero. Group 0 contributes count(N/10) (which counts all digits but the last) plus N/10 (which counts the zeroes from the final digits).

Since we are going from 1 to N instead of 0 to N, this logic breaks down for single-digit N, so we just handle that as a special case.

[update]

What the heck, let's generalize and define count(n, d) as how many times the digit d appears among the numbers from 1 to n.

/* Count how many d's occur in a single n */
unsigned
popcount(unsigned n, unsigned d) {
  int result = 0;
  while (n != 0) {
    result += ((n%10) == d);
    n /= 10;
  }
  return result;
}

/* Compute how many d's occur all numbers from 1 to n */
unsigned
count(unsigned n, unsigned d) {
  /* Special case single-digit n */
  if (n < 10) return (d > 0 && n >= d);

  /* If n does not end in 9, recurse until it does */
  if ((n % 10) != 9) return popcount(n, d) + count(n-1, d);

  return 10*count(n/10, d) + (n/10) + (d > 0);
}

The ugliness for the case n < 10 again comes from the range being 1 to n instead of 0 to n... For any single-digit n greater than or equal to d, the count is 1 except when d is zero.

Converting this solution to a non-recursive loop is (a) trivial, (b) unnecessary, and (c) left as an exercise for the reader.

[Update 2]

The final (d > 0) term also comes from the range being 1 to n instead of 0 to n. When n ends in 9, how many numbers between 1 and n inclusive have final digit d? Well, when d is zero, the answer is n/10; when d is non-zero, it is one more than that, since it includes the value d itself.

For example, if n is 19 and d is 0, there is only one smaller number ending in 0 (i.e. 10). But if n is 19 and d is 2, there are two smaller numbers ending in 2 (i.e. 2 and 12).

Thanks to @Chan for pointing out this bug in the comments; I have fixed it in the code.