Factorial Trailing Zeroes

from leetcode discussion

Because all trailing 0 is from factors 5 * 2.
But sometimes one number may have several 5 factors, for example, 25 have two 5 factors, 125 have three 5 factors. In the n! operation, factors 2 is always ample. So we just count how many 5 factors in all number from 1 to n.

n!=2 * 3 * ...* 5 ... *10 ... 15* ... * 25 ... * 50 ... * 125 ... * 250...
  =2 * 3 * ...* 5 ... * (5^1*2)...(5^1*3)...*(5^2*1)...*(5^2*2)...*(5^3*1)...*(5^3*2)... (Equation 1)

We just count the number of 5 in Equation 1.
Multiple of 5 provides one 5, multiple of 25 provides two 5 and so on.
Note the duplication: multiple of 25 is also multiple of 5, so multiple of 25 only provides one extra 5.
Here is the basic solution:

return n/5 + n/25 + n/125 + n/625 + n/3125+...;

code: 

    int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    } 

iterative:

    int trailingZeroes(int n) {
        int cnt=0;
        while(n>0){
            cnt+=n/5;
            n/=5;
        }
        return cnt;
    }