[Leetcode] Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

Analysis:

As we know, n! = n * (n-1) * (n-2) * ... * 2 * 1. A simple way to get the trailing zeros is to calculate the value of n! and then count the trailing zeros. The problem is that the value of n! is too big to be hold by an integer. Even if we express the  n! using string, its time complexity is O(N), which does not satisfy the "logarithmic time complexity". 

Observed that every pair factor 5 and 2 of the number 1 to n will contribute a trailing zero for n!. Since from 1 to n, the number of  factor 2 is always greater than the factor of 5, the number of factor 5 is the number of trailing zeros. 

So the problem becomes how many of factor 5 among the number 1 to n. We know there are n/5 factor 5 from 1 to n (named 5, 10, 15, ...., floor(n/5) * 5) and there are n/25 extra factor of 5 (named 25, 50, 75, ... , floor(n/25)*25), and n/125 extra factor of 5, and so on. It is not so difficult to implement the code and the following code explains itself. One special case to handle is the k may be exceed the INT_MAX so better to use long to avoid overflow. 

    

    int trailingZeroes(int n) {
        int count = 0;
        long k = 5;
        while(n >= k)
        {
            count+=n/k;
            k*=5;
        }
        return count;
    }