There's a nice algorithm for doing this calculation which is explained here.
If $x$ is the number we're given, $f(x)$ is the number of zeros that appear in the range $1..x$. Using a simple program we can calculate $f(x)$ for some small values to spot a pattern.
public int CountZerosInRangeOneTo(int end)
return Enumerable.Range(1, end)
.Select(i => i.ToString())
.SelectMany(s => s.ToCharArray())
.Count(c => c == '0');
f(5 ) = 0
f(52 ) = 5
f(523 ) = 102
f(5237 ) = 1543
f(52378) = 20667
If $y$ is the new single digit number added to the end each time, it would appear the following is true:
$f(10x + y) = 10 \cdot f(x) + x$
For example, if $x = 523$, $y = 7$, and $f(x) = 102$, then:
$f(10 \cdot 523 + 7) = f(5237) = 10 \cdot f(x) + x = 10 \cdot 102 + 523 = 1543$
Fantastic. However, where this breaks down is when $x$ contains zeros itself. For example:
f(3 ) = 0
f(30 ) = 3 correct
f(302 ) = 53 incorrect, expected 60, a difference of 7, or 9 - y
f(3020 ) = 823 incorrect, expected 832, a difference of 9, or 9 - y
f(30207) = 11246 incorrect, expected 11250, a difference of 4, or 2 * (9 - y)
If $g(x)$ is the number of zeros in the number $x$, then we can modify our formula like this:
$f(10x + y) = 10 \cdot f(x) + x - g(x) \cdot (9 - y)$
And that makes sense. If $x = 3020$ and $y = 7$ and not $9$, then that is two less numbers on the end of the sequence with two zeros each.
So how does this formula help? Well for a very large $x$ with thousands of digits we can go left to right through each digit and calculate $f(x)$ as we go. Here's a sample C# program to do just that.
public long CountZerosInRangeOneTo(string end)
long x = 0;
long fx = 0;
int gx = 0;
foreach (char c in end)
int y = int.Parse(new string(c, 1));
// Our formula
fx = 10 * fx + x - gx * (9 - y);
fx += Modulus; // Avoid negatives
fx %= Modulus;
// Now calculate the new x and g(x)
x = 10 * x + y;
x %= Modulus;
if (y == 0)
The limitation (in C# anyway) is $x$ and $f(x)$ will get very large, so the program will have to calculate the result modulo some number, or else use a non-native integral representation.