Factorial Trailing Zeroes (Easy)

Description

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.

Analysis

简单数论题,我们可以知道n!的最后的尾0的个数取决于n!中2和5的因子的个数。
而5的个数肯定比2要小，因此我们只要求出n!中有多少个5。
ans = [N/5] + [N/5^2] + [N/5^3]+….

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
//C++
class Solution {
public:
    int trailingZeroes(int n) {
        int sum = 0;
        while(n){
            sum+=n/5;
            n/=5;
        }
        return sum;
    }
};