Factorial - Number of 0's in 100!

A common interview question asked these days is how many zero's does 100! contain?
`
Many of us do say it is 24 ,but how many of us care to know the smart way of doing it?

And what is the same for 1000! ?

We will now look into this smart method of finding the no of zeroes in N! where N is any natural number.

One hundred factorial (100!) is a huge number of 158 digits.We add a zero to the tail of a number whenever we multiply by 10, which is 2 x 5. There are lots of twos as factors of 100!, but not as many fives, so the number of zeros will be the same as the number of fives. The factors 5, 10, 15, 20, ... each contribute a five, and 25, 50, 75, and 100 each add an extra. So the total is (100 / 5) + (100 / 25) = 24.

So the best way to calculate the number of zeroes at the end of N! is finding the number of 5's in the prime factorization of N!.

Now coming to this task of figuring out the number of 5's,

In general ,if P is any prime,then the no of P's in N! is given by
Sum (floor(n/p^i)) for p^i <= n

This apparently weird formula can be explained with ease!!

consider the numbers 1,2,3,.........,,N.Every pth number is divisible by p.So all those multiples of p put together contribute floor(N/p) to the power of p.

Similarly every p^2th number is divisible by p^2.And each of them have already contributed 1 to power of p in previous iteration,as each of them are divisible by p.So each of them contribute an additional 1, which means they all together contribute floor(N/p^2) to the already sum.

These terms of contribution go on till we have p^i <= N,hence the summation
Sum (floor(n/p^i)) for p^i <= n

Now, the statement no of 5's in 100! =floor(100/5)+floor(100/25) is easily understood.

Now coming to the task of calculating no of 0's in 1000!.
It is given by S= floor(1000/5) + floor(1000/25) + floor(1000/125) + floor(1000/625)=249.

Well having made this task simple,we shall look at questions based on this.

Questions

1) write a program that can compute the last non-zero digit of any factorial for ( 0 <= N <= 10000). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce 2 because 5! = 120, and 2 is the last nonzero digit of 120.
Click Here For Solution


2)If you have already solved the above problem, then give a generalized method to find the last x non-zero digits of N factorial
Click Here For Solution