172. 阶乘后的零

Problem: 172. 阶乘后的零

思路

要求阶乘中0的个数，就是求其因子10的个数。因子10的个数又等于质因子2和质因子5个数的最小值，并且由接下来的证明可以知道，质因子2的个数一定大于等于质因子5的个数，因此我们只需求出质因子5的个数即可。

如何证明呢？我们考察1-n中所有整数的质因子p的个数和。

我们先从p的1次方开始， 可以算出1-n所有数中一次方的个数和为n除以p的下取整，把这些因子加上。同理二次方为n除以p的平方的下取整，而在计算平方时，其中一次方的因子我们前面已经计算过了，因此只加上一个因子。接下来的次方同理。

把这些个数加起来，我们就可以算出质因子p的总个数。由于每次都除以p的若干次方，p越小其质因子个数就越多，因此质因子2的个数一定大于等于质因子5的个数。

而且算出了这个总个数后，我们就可以通过每次都把n除以5，并把结果加上来模拟上述计算过程。

复杂度

• 时间复杂度: $O(logn)$
• 空间复杂度: $O(1)$

Code

[]

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