Factorial Trailing Zeroes

172. Factorial Trailing Zeroes

Difficulty: Easy

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

Note: Your solution should be in logarithmic time complexity.

求n!中，末尾0的个数

等价 n!= a10^k= a5^k*2^k

因为10的因子只能是2和5，而每5个数之间，必定有2，所以只要数5的倍数的个数就好了
n/5 + n/25 + n/125 + n/625 + n/3125+…

Solution

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while(n>0){
            count +=n/5;
            n/=5;
        }
        return count;
    }
};