LeetCode

Factorial Trailing Zeroes

2015.1.23 18:46

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

Note: Your solution should be in logarithmic time complexity.

Solution:

　　The number of zeros is simply the number of 5s. That's it.

　　Time complexity is O(log(n)), space complexity is O(1).

Accepted code:

// 1AC, log5(N)
class Solution {
public:
    int trailingZeroes(int n) {
        int sum;
        
        sum = 0;
        while (n > 0) {
            sum += n / 5;
            n /= 5;
        }
        
        return sum;
    }
};