Factorial Trailing Zeroes

Posted on October 17, 2016

Problem

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Solution

0 in the number is coming from 10. 10 = 2 * 5. So must count the number of 2*5 pairs in n!.

The naive way is to use n! % 5 each time, add the counter until n! % 5 != 0. However, n! is easy to overflow. So this problem we cannot do the calculation of n!.

To count the number of 5, we can just use the result of n/5.                                                          i.e. 5! -> 5/5 = 1        10! -> 10/5 = 2  However, for 25! or 125! or (5^x)!, this includes 25, 125, some 5^x numbers contain more than one 5. So need to add these concealed 5 together. Therefore, the total number of 5 is n/5 + n/25 + n/125 + …. until 5^x > n.

After the judgement of OJ, when n is too big, it means 5^x may get too big to overflow, so the parameter to store this number (i) must be set as long type to avoid overflow.