c - 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