Tuesday, July 22, 2014

Number of trailing zeros in a factorial

This problem looks easy to solve for small numbers. Simply calculate the factorial and count how many zeroes are present at the end!

But the factorial grows big very fast even for small numbers which cannot fit into standard data types. (20! = 2432902008176640000. Cannot fit into a long variable also). In summary this is not the best approach that one can think of.

We can use some simple mathematical properties to solve this problem easily and efficiently. 

Can you think how can a factorial value gets a zero at the end?

If two numbers, one, a multiple 5 and and the other a multiple of 2 are multiplied, it contributes a zero at the end in the product.

For example 2*5, 14*15, 26*25 etc...

So our job is to calculate number of such pairs. Since the multiples of 2 will always be greater than multiples of 5, We can simply count 5-multiples which divide the given number. This is simply (number/5)

But the problem is not yet over!
How many zeroes does a 25 contribute?
Let us consider 26! = 1 * 2 * ...5 * 6...*25*26

It can be re written as 
1 * 2 *...* 23 * (12* 2) * (5 * 5) * (2 * 13)

It contributes to two zeroes!

Similarly we can observe that 125 contributes to 3 zeroes and so on...

So as a conclusion, the result is the sum of 5 multiples, 25 multiples, 125 multiples etc... which are also divisors of the given number.

Here is the C++ implementation of the above solution.