Fog Creek Software
Discussion Board




100! even easier

The solution presented considered four different cases--factors of 10, "factors of 5" (by which he obviously meant things ending in 5), and factors of 25.  The solution rightly recognizes that there should be enough factors of 2 to compensate and make 0 digits.

But the problem is much easier than this.  There are 20 factors of 5 (count things divisible by 5, by doing 100/5=20), and enough 2's to make trailing digits from those.  The only other case to consider is the factors of 25.  These are actually part of the same 20 numbers--in fact, every 5th factor of 5 (20/5=4).  So you only need to consider two cases; furthermore, a general solution is more obvious for the number of trailing zeroes for, say, 1000! (200 + 40 + 8 + 1).

anonymous
Monday, January 03, 2005

anonymous,

where does the 8 and 1 come from in (200+40+8+1)?

so for 10000 it would be (2000+400+80+16+3)?

jazzy
Monday, January 10, 2005

I think it came from dividing by five from the previous number, and taking only the integer part if the division has non-zero remainder.

So to get (200+40+8+1)
first 1000/5 = 200
next 200/5 = 40
then 40/5 = 8
finally 8/5 = 1.6 truncate to 1

As suggested, following the same procedure for 10000, the result would be (2000+400+80+16+3).

JHY
Monday, January 10, 2005

sorry,

shouldve mentioned in earlier post that I did understand where they came from (dividing each by 5) but what is the explanation for e.g. i understand that theyre 200 factors of 5- agree, they are 40 factors of 25- agree,

now theyre 8 factors of what?

8 factors of 250 (which is untrue) or of 125(which is true)? but these factors of 125 have already been accounted for (40 factors of 25) havent they?

jazzy
Thursday, January 13, 2005

We are concerned with factors of five.  So 5, 10, 15, 20, 25, 30, 35, ... contain factors of five.  We count up to 1000; there are 200 of them.

Then we notice that some of these numbers contain more than one factor of five.  For example, 25, 50, 75, 100, 125, 150, 175, 200, ... contain more than one factor of five.  We must count the second factor in those numbers, too.  These are numbers that contain two or more factors of five.  There are 40 of them.

Naturally we want to see if there are numbers with three or more factors of five, and count the third factor of five in those numbers.  They are 125, 250, 375, 500, 625, 750, 875, 1000.  There are 8 of them.

Then we see that there is one number with four factors of five, namely 625.

Finally we see that there are no number from 1 to 1000 which has five factors of five or more, so we are done counting.  The sum is 200 + 40 + 8 + 1.

The idea is that numbers such as 25 = 5^2, which has two factors of five, we must count it twice.  And indeed we did count it twice, once in 200 and once in 40.

Numbers such as 500 = 5^3 * 4, which has three factors of five are counted three times, once in 200, once in 40, and once in 8.

JHY
Thursday, January 13, 2005

An even easier calculation

Below is just a convoluted summation from i = 1 to INF of Math.floor(n/5^i), when determining the number of trailing zeros in n!

int NumTrailingZerosInFactorial(int n)
{
    int numTrailingZeros = 0;
    int factor = 5;
    for (int i = 1, i < Math.floor(log(5,n)), ++i)
    {
          numTrailingZeros += Math.floor(n / factor);
          factor *= 5;
    }
    return numTrailingZeros;
}

Where log(5,n) is log base-5 of n. 

Basically, we count the number of 5s in n.  We do not need to count the number of 10s (since this includes 5s), and there are plenty of 2s to pair up with the 5s.  This is an undercount however, so we need to count the numbers which contain two factors of 5 (e.g. 25, 50, 75, etc).  Then account for the numbers which have three factors of 5 (e.g. 125, 250, etc), and so on.  Bascially, factor is just 5^i, and this is just a summation from 1 to INF, but know when to stop (alternatively, we could also stop when n < factor).


EX: 130!

i=1
Math.floor(130/5) = 26
i=2
Math.floor(130/25) = 5
i=3
Math.floor(130/125) = 1
DONE

So the number of trailing zeros in 130! is 26+5+1 = 32.

Eric Ott
Wednesday, March 09, 2005

*  Recent Topics

*  Fog Creek Home