【LeetCode每日一题】172. 阶乘后的零【中等】脑筋急转弯

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3 输出：0 解释：3! = 6 ，不含尾随 0 示例 2：

输入：n = 5 输出：1 解释：5! = 120 ，有一个尾随 0 示例 3：

输入：n = 0 输出：0  

提示：

0 <= n <= 104

题解： 这道题的第一个解法其实很好想，因为能够产生0的只有2和5，所以统计2和5的个数就可以了。

class Solution {
public:
    int trailingZeroes(int n) {
        int cnt2 = 0, cnt5 = 0;
        for(int i = 1; i <= n; i++){
            int tmp = i;
            while(tmp % 2 == 0){
                cnt2++;
                tmp /= 2;
            }
            while(tmp % 5 == 0){
                cnt5++;
                tmp /= 5;
            }
        }
        return min(cnt2, cnt5);
    }
};

但是还有一个比较巧妙的方法，因为2的个数肯定比5的多，所以统计5的个数就可以了。

class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        for (int i = 5; i <= n; i += 5) {
            for (int x = i; x % 5 == 0; x /= 5) {
                ++ans;
            }
        }
        return ans;
    }
};

上述方案的时间复杂度为O(n)，空间复杂度为O（1）。

但是实际上还有一个更加巧妙的方法，可以将时间复杂度降到O（logn）。 可以通过不断将 n 除以 5，并累加每次除后的 n，来得到答案。

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