Algorithm

LintCode/Trailing Zeros

Problem Summary

Find the number of trailing zeros in N! (N factorial).

Solution

Apparently, the answer is equal to the number of 5 in N!, e.g. N/5 + N/(5^2) + N/(5^3) + … + N/(5^c), where 5^c ≤ N < 5^(c+1).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    /*
     * @param n: A long integer
     * @return: An integer, denote the number of trailing zeros in n!
     */
    long long trailingZeros(long long n) {
    	long long count5 = 0 , fac = 5;
    	while (n>=fac) {
    		count5 += n/fac;
    		fac *= 5;
    	}
    	return count5;
    }
};