Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
oeis.org/A061217 –  Charles Nov 10 '11 at 21:36

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer
1  
OMG! Thank you very much. I understood your logic but wondering how did you get it? I have scratched my head more than two hours but wasn't nearer to figure out what to do when number of digits cross the length 10 as I can't do anything with 10C11 :) –  AppleDeveloper Nov 10 '11 at 23:23
2  
@AppleDeveloper: There was a Car Talk puzzler some time ago about counting how many zeros show up in an odometer going from x to y; I did a complicated counting argument; when Ray Mazzoli gave the answer, he mentioned the clever trick of realizing that every digit occurs the same number of times overall and taking the average. That was my starting point here. The really tricky bit is to handle those "partial ranges" when your top number is not of the form $99\cdots999$. –  Arturo Magidin Nov 11 '11 at 1:34
    
Cool. Thank you very much Arturo! –  AppleDeveloper Nov 13 '11 at 9:41

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.

share|improve this answer
    
You are right - here is a Mathematica code to check With[{x = 751}, Count[Flatten[IntegerDigits /@ Table[x - n, {n, 0, x - 1}]], 0]] –  no identity Oct 17 '12 at 5:50

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.