# Count the Zeros

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)

• How are you going to measure the speed of the submissions? Jan 9, 2014 at 18:42
• Most efficient algorithm. Jan 9, 2014 at 19:11
• @Xinbi most efficient isn't particularly well defined. Do you mean in Big O complexity? Benchmark? If we measure straight time, it's unfair if I have an 8 core processor and parallelise this. Jan 9, 2014 at 19:26
• I got an O(1) solution. Do I win now? xD Jan 9, 2014 at 21:03
• I agree with @Cruncher's approach to game a Big-O challenge with a massive lookup table. It's foolish to not freely spend a free resource if it helps your answer. RAM, code space, and setup time, in this problem specification, are all free. A pure lookup approach may be practically impossible but a hybrid solution of lookup/computation could be the best in practical implementation. Jan 9, 2014 at 22:38

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.

• Unfortunately, I don't think there's a computer out there that can hold an array of ten tremilliatrecendotrigintillion integers. Jan 9, 2014 at 21:04
• @Xinbi I don't believe a computer being able to run it was in the requirements. This program provably works, even if I can't run it. Jan 9, 2014 at 21:06
• No. The generation is there, simply because I cannot write the program here. It's vastly too big. It doesn't mean that the program doesn't conceptually exist. (FYI, O(n+1) is nonsense. It's just O(n)) Jan 9, 2014 at 21:12
• @Xinbi actually. I would argue that the generating code is O(1) as well. It takes NO input, therefore there is no n. So it's O(1) by default. It will take the same amount of time every time you run it. for(i=0;i<1000000;i++){print("hi")} Is O(1) for the same reason. Unless you accept the number as an input. Jan 9, 2014 at 21:19
• @SergeyS If there was no upper bound constraint, then an O(1) solution would be impossible for this problem. The O(1) is entirely a product of the bound. It's a bit of a rule abuse. Oh well. Jan 9, 2014 at 21:54

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)3log 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.

• I agree with your assessment. My O(Log(n)) solution came up with the same answer as yours. (I didn't look close enough at the resulting digits) Jan 10, 2014 at 1:02

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

• Won't this skip 101? Jan 9, 2014 at 20:27
• Most efficient algorithm wins (Big O complexity). Jan 9, 2014 at 20:33
• It does. Why didn't I thought of it? Jan 9, 2014 at 20:33
• I updated my code and it should be right and faster now. Jan 9, 2014 at 22:47
• It gives the wrong answer, why it is accepted? Jan 10, 2014 at 0:48

# 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.

• I borrowed your code for generating my solution btw Jan 9, 2014 at 21:45
• @Cruncher Big deal since I don't know Big O (whatever that is).
– user10766
Jan 9, 2014 at 21:46
• en.wikipedia.org/wiki/Big_O_notation if you're interested it all. It's very academic. It's a way of formally measuring the complexity of algorithms. Not always a good metric in practice though (as evidenced by my perfect solution.) O(1) is the smallest complexity. It means constant time. Jan 9, 2014 at 21:49
• Sure, thanks. (extra length)
– user10766
Jan 9, 2014 at 21:49
• Theoretically. My solution has lower complexity than yours. And by the winning condition of this question is better than yours. Even though its always slower. My answer was to point out the flaws in the question Jan 9, 2014 at 22:07

# Haskell - O(n) for 10^n input

import Data.Char
import Data.List

p n = (10^n-10)div9 -- 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)


• Comparing your answer to mine, it seems like one of us is off by one. Did you perhaps include the number 0 in the count? Do you get the correct result of 11 for input 100?
– MvG
Jan 10, 2014 at 0:59
• @MvG It indeed counts the first 0 as I didn't read the problem carefully, now it's fine. Jan 10, 2014 at 1:09
• @swish now it's the correct value. Yay! Jan 10, 2014 at 1:12

# 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.

## Python O(log10 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 log10 n iterations are needed to reach the final answer.