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.

Answer 3

Let Z(n) = #zero digits in numbers 0 <= k < n. Obviously, Z(0) = 0.

If n = 10*k + r, 0 <= r <= 9, all 10*k numbers 10*j + s, 0 <= j < k, 0 <= s <= 9 are in the range, each tenth last digit is 0, so that's k zeros, and each prefix j (all but the last digit) occurs ten times, but we mustn't count 0, so the number of zeros in the prefixes is 10*(Z(k)-1).

The number of zeros in the r numbers 10*k, ..., 10*k + (r-1) is r*number of zeros in k + (r > 0 ? 1 : 0).

So we have an O(log n) algorithm for computing Z(n)

unsigned long long Z(unsigned long long n)
{
    if (n == 0) {
        return 0;
    }
    if (n <= 10) {
        return 1;
    }
    unsigned long long k = n/10, r = n%10;
    unsigned long long zeros = k + 10*(Z(k)-1);
    if (r > 0) {
        zeros += r*zeroCount(k) + 1;
    }
    return zeros;
}

unsigned zeroCount(unsigned long long k)
{
    unsigned zeros = 0;
    while(k) {
        zeros += (k % 10) == 0;
        k /= 10;
    }
    return zeros;
}

To compute the number for an arbitrary range,

unsigned long long zeros_in_range(unsigned long long low, unsigned long long high)
{
    return Z(high+1) - Z(low); // beware of overflow if high is ULLONG_MAX
}

Answer 4

I have a very simple way to do count 0's in between 1 to n. I hope this will solve your issue and remove complexity

function countZero(n) {
  var count = 0;
  while (n > 0) {
    count += Math.floor(n / 10);
    n = n / 10;
  }
  console.log(count);
}

countZero(99);

Answer 5

class FindZero{

    public int findZero(int lastNumber){

        int count=1,k;
        if(lastNumber<10)
            return 0;
        else if(lastNumber==10)
            return 1;
        else{

            for(int i=11;i<=lastNumber;i++){
                k=i;
                while(k>0){

                    if(k%10==0)
                        count++;
                        k=k/10;
                }
            }
            return count;
        }
    }
    public static void main(String args[]){
        FindZero obj = new FindZero();
        System.out.println(obj.findZero(1234));
    }
}

Answer 6

# in single loop without using inbuilt functions

def func(n):
  lst=list(range(0,n+1)) #make list from 0 to n

  strng=str(lst) #convert list into string

  strng=strng[1:-1] #remove first and last square braces from string

  strng=strng.replace(",","") #remove commas

  strng=strng.replace(" ","") #remove spaces

  #now this is the complete string from 0 to n number
  count=0
  num=0
  for i in strng:
    if i==str(num):
      count += 1
  print(count)
func(10)

#Azizullah Ali

Answer 7

The way I approached this problem:

numbers can be in the range 1 to N:

So, I broke this into ranges like this:

Rangle      : #Digits   :   #Zeros
1   -   9   :   1       :   0
10  -   99  :   2       :   9 (number of all the possible digits when zero is at units place=> _0 ie, 1,2,3,4,5,6,7,8,9
100 -   199 :   3       :   20 => 10 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
200 -   276 :   3       :   18 => 8 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
300 -   308 :   3       :   10 => 1 (#digits when zero is at units place) + 9 (#digits when zero is at tens place)
1000-   1008:   4       :   19 => 1 + 9 + 9

Now for any given range 1 - N, I want to be able to break the number into these ranges and use the above logic to compute the number of zeros.

Test run:

for a given number N:

- compute number of digits: len
- if len = 1 : d1: return 0
- len = 2: d2_temp: count # of digits that can possibly occur when 0 is at unit's place 
            : for e.g. 76: so numbers can be between 10 - 76: (7 - 1) + 1 = 7
         : d2: sum(d2_temp, d1)
- len = 3: return d3 : sum(d3_temp, d2)
         : compute d3_temp: 
         : for e.g. n = 308 : get digit at 10^(len-1) : loopMax 3
         : d3_temp1: count number of zeros for this loop: 1 * 100 to (loopMax -1) * 100 : (loopMax-1) * 20
         : d3_temp2: for n count (#digits when zero is at units place) + (#digits when zero is at tens place)
         : d3_temp = d3_temp1 + d3_temp2

Lets try to generalise:

99 : sum( , )
    : d3_temp: 
    : loopMax: n = 99 : n/(10^1) : 9
    : d3_temp1: 8 : (9-1) * (10*(len-1)) : (loopMax - 1) * 10 * (len-1)
    : d3_temp2: 1 : for len, count #0s in range (loopMax * 10 * (len-1)) to n : count(90, 99)
    : d3_temp = 8 + 1
    : sum(9, 0)
    : 9

I'm having some trouble proceeding from here, but this would work.