factorial-trailing-zeroes

Factorial Trailing Zeroes – LeetCode 172

Problem

Description

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

Note: Your solution should be in logarithmic time complexity.

Answer

Original

Code

class Solution {
public:
    int trailingZeroes(int n) {
        unsigned r = 0;
        for(long long i = 5; n / i > 0; i *= 5)
            r += n / i;
        return r;
    }
};

思路

求末尾的零，就是求因数中能生成多少个10,就是求所有因数中能形成多少对2和5,考虑到5的个数远多于2,故求因数中总共有多少个5。于是搞定，时间复杂度$O(log_{5}{n})$，空间复杂度$O(1)$。
耗时$3$ ms，排名$92.96\%$

Better

思路

暂时还没看到更好的方法。