欢迎访问LeetCode题解合集

题目描述

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

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

阶乘的末尾有多少个 0 ，跟因子 2 和 5 有关，而在 $1∗2∗3∗..∗n$ 中，因子 2 的数目要多于因子 5 的数目，所以只需要统计 1~n 中多少个因子 5 即可。如果直接遍历 1~n ，统计每个数的因子 5 数目，则时间复杂度 $O(nlog_5^{n})$ 。

假设 n 为 125，则我们会发现：

5、10、15、20、25、…、125，含一个因子 5

25、50、75、100、125，含两个因子 5

125，含三个因子 5

通过上面规律可以发现，n! 中的因子 5 的总个数为：$n/5+n/5^2+n/5^3+…+n/5^i$

一直到 $n > {5^i}$ 停止。

时间复杂度：$O(log_5^n)$

额外空间复杂度：$O(1)$

class Solution {
public:
    int trailingZeroes(int n) {
        int ret = 0;
        while ( n ) {
            n /= 5;
            ret += n;
        }
        return ret;
    }
};
/*
时间：0ms，击败：100.00%
内存：5.8MB，击败：85.89%
*/