4
$\begingroup$

Could anyone please tell me what could be the math function to get the number of zeros in given decimal representation of numbers? I scratched my head on Combination and Permutation but couldn't come up with generic answer. The number length can be up to 1000 digits, so you can represent a number as a String.

For example, if numbers range is $1-100$, the answer should be $11$, for $1-200$, it's $20$ and so on! Now, how would you find total number of zeros between $1-19447494833737292827272\cdots 444$ ( or any big number)?

Thanks.

  • 0
    http://oeis.org/A0612172011-11-10

3 Answers 3

7

Say you are writing all $d$ digit numbers, writing leading zeros. Then you would write out $d\times 10^d$ digits total, with each digit occurring exactly $\frac{1}{10}$th of the time, so you would write a total of $d\times 10^{d-1}$ zeros.

So, for example, to write all numbers between $0$ and $99$, writing the numbers less than $10$ as $0d$, you would write $2\times 10^2 = 200$ digits, of which $2\times 10=20$ are zeros.

Of course, of these you don't want to count the leading $0$s of $00-09$, so you subtract $10$; and you don't want to count the second $0$ from $00$, so you subtract another one, giving you a total of $9$ zeros. So you need to adjust the count above.

If you write all numbers of up to $d$ digits, then the number of $0$s, including leading $0$s, is $d\times 10^{d-1}$. Then you subtract the number of leading $0$s that appear in the left-most digit (there are $10^{d-1}$ of them), those that appear in the second-left-most digit when the left-most is $0$ (there are $10^{d-2}$ of them); those that appear in the third left-most digit when the first two are $0$ (there are $10^{d-3}$ of them) and so on. So you get $d\times 10^{d-1} - (1+10+10^2+\cdots + 10^{d-1}) = \frac{(9(d-1)-1)10^{d-1} + 1}{9}.$ So, for example, for $d=2$ (from $1$ through $99$), you get $\frac{(9-1)10^1 + 1}{9} = \frac{81}{9} =9,$ same as above. For $d=3$, (from $1$ through $999$) you get $\frac{(9(2) - 1)10^2 + 1}{9} = \frac{1701}{9} = 189.$

What if you are doing something slightly different, as you write, say, only the numbers between $1$ and $751$?

You can count the zeros from $1$ to $99$ as above.

Then count the number of zeros in numbers of the form $7bx$ with $1\leq b\leq 5$. There's one for each value of $b$, for a total of $5$.

Then count the number of zeros in numbers of the form $70x$; there's $11$ of them.

Then count the number of zeros in numbers of the form $axy$ with $1\leq a\leq 6$; there's $10^{2-1}=10$ of them (you are just counting all zeros in numbers up to 2 digits, counting leading $0$s).

So after counting all the way to $99$, you then add:

  1. One zero for each number $7bx$, $1\leq b\leq 5$: total, $5$ (the middle digit of $751$).
  2. Zeros for each number $70x$; total, $11$.
  3. Zeros for each number $axy$ with $1\leq a\leq 6$; total, $6\times 10^{2-1} = 60$.

There are 9 zeros from $1$ through $99$; and then there are $60+11+5=76$ zeros from $100$ through $751$, for a total of $85$ zeros from $1$ through $751$.

  • 0
    Cool. Thank you very much Arturo!2011-11-13
3

The approach is correct, but the answer is wrong. There are 145 zeros from 1 to 751: 9 zeros from 1 to 99, 120 zeros from 100 to 699 (20 x 6) and 16 zeros from 700 to 759

Total: 9+120+16 = 145.

  • 0
    You are right - here is a Mathematica code to check With[{x = 751}, Count[Flatten[IntegerDigits /@ Table[x - n, {n, 0, x - 1}]], 0]]2012-10-17
0

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.