Count the Zeros

Question

For a given n, count the total number of zeros in the decimal representation of the positive integers less than or equal to n. For instance, there are 11 zeros in the decimal representations of the numbers less than or equal to 100, in the numbers 10, 20, 30, 40, 50, 60, 70, 80, 90, and twice in the number 100. Expect n to be as large as 10^10000.

Your task is to write a program to count zeros. Most efficient algorithm wins (Big O complexity)

EDIT: post your code and your answer for n = 9223372036854775807.

Answer 1

Some thoughts up front:

f[i]: number of zeros in [10^i, 2*10^i)
g[i]: number of zeros in [10*10^i, 11*10^i)
h[i]: number of zeros in [0, 10^i)

i   f       g     h
1  1*     10*     *
2  1**    10**    **
3  1***   10***   ***
4  1****  10****  ****

f[i] = 9*f[i - 1] + g[i - 1]
g[i] = f[i] + 10^i
h[i] = h[i - 1] + 9*f[i - 1]

Now the code:

def zeros(n):
    s = str(n)
    f = [0]
    g = [1]
    h = [0]
    for i in range(1, len(s) + 1):
        f.append(9*f[-1] + g[-1])
        g.append(f[-1] + 10**i)
        h.append(h[-1] + 9*f[-2])
    k = len(s) - 1
    a = h[k]                  # all numbers with fewer digits
    a += (int(s[0]) - 1)*f[k] # same number of digits but first digit less
    s = s[1:]
    while s:
        if s[0] == '0':
            a += int(s) + 1
        else:
            a += int(s[0])*f[len(s) - 1] + 10**(len(s) - 1)
        s = s[1:]
    return a

For n = 9223372036854775807 the result is 16577013372932555466. This is different from the currently accepted answer by @user14325, but I have more trust in it since starting at n=1000, @user14325 disagrees from the naive implementation suggested by @user2509848 in which I have a lot of trust due to its simplicity.

Complexity of my code is O(log n), at least if you assume uniform cost for arithmetic operations. Taking bit cost into account, it will probably be O(log(n)³log log(n)) or something like that, depending on how Python does its big integers and the exponentiation on them. If you care about the constants, then there is a lot of room for optimizations. Converting between numbers and strings all the time is hardly efficient. But as long as you only care for asymptotic behavior, I'll leave it at that.

Answer 2

Python O(1):

Since the challenge has been specified to be using Big O. I concluded that the best way to do it(since the upper bound is limited by a constant) is to just to create a giant look-up array.

However, this program would be too big to post here, so I made a program that generates it:

def zeroesUpToN(n):
    zeros = 0
    for i in range(n):
        s = str(i+1)
        zeros += s.count('0')
    return zeros

s = "print(["
for i in range(10^10000):
    s += str(zeroesUpToN(i+1)) + ",";
s = s[:-1] + "][int(input())])"

print(s)

So, this will ALWAYS take a long time to run(I mean the resulting program, not the generating program. The generating program would take even longer). But, how long it takes to run will not depend on n. Therefore, by definition it is an O(1) solution.

Here is an actual program that works for smaller outputs(up to 200):

print([0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,11,12,13,14,15,16,17,18,19,20,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,26,26,26,26,26,26,26,26,26,26,27,27,27,27,27,27,27,27,27,27,28,28,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,29,29,31][int(input())])

The real one is obviously much bigger.

P.S This is the problem with Big O problems.

EDIT: Oops, I forgot to give credit to @user2509848 whom I actually stole the code for generating each N.

Answer 3

Java:

public class ZeroCount {
    static final int max = 65498;

    public static void main(String[] args) {
        int res = 0;
        for (int i = 10; i <= max; i*=10) {
            res += max/i + max/(10*i) * (i-1);
            res -= (max % (10*i) < i) ? (i-1) - (max % i) / (i/10) : 0;
        }
        System.out.println(res);
    }
}

Should be O(log(n))

Edit:

For n=9223372036854775807 I decided to use Python instead of Java since 9223372036854775807 is Long.MAX_VALUE in Java and I didn't want to use BigInt

def zeros(n):
    res = 0
    i = 10
    while i <= n:
        res += (n // i) + n // (10 * i) * (i - 1)
        res -= (i - 1) - (n % i) if n % (10 * i) < i else 0
        i *= 10
    return res

print(zeros(9223372036854775807))

> 16577013372932555466

Answer 4

Python 3

n = int(input())
zeros = 0
for i in range(n):
  s = str(i+1)
  zeros += s.count('0')

print(zeros)

Fast up to 10,000,000. It gets slower when I bring it to 100,000,000.

Answer 5

Haskell - O(n) for 10^n input

import Data.Char
import Data.List

p n = (10^n-10)`div`9 -- number of padded zeroes below 10^n
t n = n*10^(n-1) -- number of zeroes below 10^n with padded
digsToInt = foldl1 (\x y -> x*10+y)

-- number of zeroes below n
f :: Integer -> Integer
f n = h ds (len - 1) - p len 
  where
  ds = map (fromIntegral . digitToInt) $ show n
  len = genericLength ds
h [x] _ = 0
h (x:ys) n | x == 0 = 1 + digsToInt ys + h ys (n-1)
           | otherwise = t (n+1) - (10-x) * t n + h ys (n-1)

Answer for 9223372036854775807 is 16577013372932555466.

Answer 6

C# O(log n):

using System;

namespace Zeroes
{
    class program
    {
        static void Main(string[] a)
        {
            int n = int.Parse(a[0]);
            int result = 0;
            for (int i = 1; i < Math.Log(n); i++) 
                result += n/(int)Math.Pow(10, i);
            Console.Write(result);
        }
    }
}

Only works for integers, of course, but the logic's sound. I have a feeling there's a better algorithm to be found, though. Nope, there's a bug in this.

Answer 7

Python O(log₁₀ n)

def zerosA(n):
  '''finds the number of zeros from [1, 10**n]'''
  if n < 1: return 0
  return 10*zerosA(n-1) + 10**(n-1) - 9*(n-1)

def zerosB(n):
  '''finds the number of zeros from (10**n, 2*10**n]'''
  if n < 1: return 0
  return 10**n + n*10**(n-1) - 1

def zerosC(n):
  '''finds the number of zeros from (2*10**n, 3*10**n]'''
  if n < 1: return 0
  return n*10**(n-1)

def count_zeros(n):
  p = z = 0
  while n >= 10:
    n, r = divmod(n, 10)
    if r > 0:
      z += zerosB(p) + zerosC(p)*(r-1) + `n`.count('0')*r*10**p
    p += 1
  z += zerosA(p) + zerosC(p)*(n-1)
  return z

if __name__ == "__main__":
  print count_zeros(9223372036854775807)

Output:

 16577013372932555466

For the number 12345, for example, this works in the following manner:

[12341, 12345] ⇒ 0
[12301, 12340] ⇒ 13
[12001, 12300] ⇒ 159
[10001, 12000] ⇒ 1599
[1, 10000] ⇒ 2893

For a total sum of 4664. No more than log₁₀ n iterations are needed to reach the final answer.