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'); }
For example:
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) gx++; } return fx; }
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.