Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

Solution:

A trailing zero is always produced by prime factors 2 and 5. If we can count the number of 5s and 2s, our task is done. However, the number of 2s is always equal to or more than the number of 5s. So we only need to count the number of 5s. 

问题转化为求阶乘过程中质因子5的个数，但是要注意25能提供2个5,125能提供3个5....count= floor(n/5) + floor(n/25) + floor(n/125) + ....

public class Solution {
    public int trailingZeroes(int n) {
        if(n == 0)
            return 0;
        
        int count = 0;
        for(long i = 5; n / i >= 1; i *= 5) {  //use long to avoid overflow
            count += n / i;
        }
        
        return count;
    }
}