172. 阶乘后的零 : 经典统计质因数运用题

题目描述

这是 LeetCode 上的 172. 阶乘后的零 ，难度为 中等。

Tag : 「数学」

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

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1n!=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 <= 10^40<=n<=104

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

数学

对于任意一个 n!n! 而言，其尾随零的个数取决于展开式中 1010 的个数，而 1010 可由质因数 2 * 52∗5 而来，因此 n!n! 的尾随零个数为展开式中各项分解质因数后 22 的数量和 55 的数量中的较小值。

即问题转换为对 [1, n][1,n] 中的各项进行分解质因数，能够分解出来的 22 的个数和 55 的个数分别为多少。

为了更具一般性，我们分析对 [1, n][1,n] 中各数进行分解质因数，能够分解出质因数 pp 的个数为多少。根据每个数能够分解出 pp 的个数进行分情况讨论：

• 能够分解出至少一个 pp 的个数为 pp 的倍数，在 [1, n][1,n] 范围内此类数的个数为 c_1 = \left \lfloor \frac{n}{p} \right \rfloorc1=⌊pn⌋
• 能够分解出至少两个 pp 的个数为 p^2p2 的倍数，在 [1, n][1,n] 范围内此类数的个数为 c_2 = \left \lfloor \frac{n}{p^2} \right \rfloorc2=⌊p2n⌋
• ...
• 能够分解出至少 kk 个 pp 的个数为 p^kpk 的倍数，在 [1, n][1,n] 范围内此类数的个数为 c_k = \left \lfloor \frac{n}{p^k} \right \rfloorck=⌊pkn⌋

我们定义一个合法的 kk 需要满足 p^k \leqslant npk⩽n，上述的每一类数均是前一类数的「子集」（一个数如果是 p^kpk 的倍数，必然是 p^{k-1}pk−1 的倍数），因此如果一个数是 p^kpk 的倍数，其出现在的集合数量为 kk，与其最终贡献的 pp 的数量相等。

回到本题，n!n! 中质因数 22 的数量为 :

\sum_{i = 1}^{k_1}\left \lfloor \frac{n}{2^i} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor + \left \lfloor \frac{n}{2^2} \right \rfloor + ... + \left \lfloor \frac{n}{2^{k_1}} \right \rfloori=1∑k1⌊2in⌋=⌊2n⌋+⌊22n⌋+...+⌊2k1n⌋

n!n! 中质因数 55 的数量为 :

\sum_{i = 1}^{k_2}\left \lfloor \frac{n}{5^i} \right \rfloor = \left \lfloor \frac{n}{5} \right \rfloor + \left \lfloor \frac{n}{5^2} \right \rfloor + ... + \left \lfloor \frac{n}{5^{k_2}} \right \rfloori=1∑k2⌊5in⌋=⌊5n⌋+⌊52n⌋+...+⌊5k2n⌋

由 2 < 52<5，可知 k_2 \leqslant k_1k2⩽k1，同时 ii 相同的每一项满足 \left \lfloor \frac{n}{5^i} \right \rfloor \leqslant \left \lfloor \frac{n}{2^i} \right \rfloor⌊5in⌋⩽⌊2in⌋，可知最终 \sum_{i = 1}^{k_2}\left \lfloor \frac{n}{5^i} \right \rfloor \leqslant \sum_{i = 1}^{k_1}\left \lfloor \frac{n}{2^i} \right \rfloor∑i=1k2⌊5in⌋⩽∑i=1k1⌊2in⌋，

即质因数 55 的个数必然不会超过质因数 22 的个数。我们只需要统计质因数 55 的个数即可。

代码：

class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
}
复制代码

class Solution:
    def trailingZeroes(self, n: int) -> int:
        return n // 5 + self.trailingZeroes(n // 5) if n else 0
复制代码

• 时间复杂度：O(\log{n})O(logn)
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.172 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。