0172. Factorial Trailing Zeroes =============================== 题目信息 -------- :题号: 0172. 阶乘后的零 :难度: Medium :主题: 数学、质因数计数、整除 :原题: `LeetCode 0172 `_ :重点: 把巨大阶乘的末尾结构转化为因子 5 的分层计数,并用连续整除避免幂次溢出 题目重述 -------- 给定非负整数 ``n``,返回 ``n!`` 的十进制表示末尾连续零的数量。 ``0! = 1``,所以 ``n = 0`` 时答案为 0。进阶要求在优于 ``O(n)`` 的时间内完成。 自建示例 -------- .. code-block:: text 输入:n = 5 输出:1 5! = 120,末尾有一个零。 .. code-block:: text 输入:n = 25 输出:6 5、10、15、20 各贡献一个因子 5,25 = 5² 额外再贡献一个,共 6 个。 .. code-block:: text 输入:n = 3 输出:0 3! = 6,没有因子 10。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int trailingZeroes(int n) { int trailing_zeroes = 0; int remaining = n; while (remaining > 0) { remaining /= 5; trailing_zeroes += remaining; } return trailing_zeroes; } }; 题解 ---- 计算阶乘做了哪些无用工作 ~~~~~~~~~~~~~~~~~~~~~~~~ 从定义出发,可以先计算 ``1 * 2 * ... * n``,再不断除以 10 或把结果转成字符串统计末尾 零。这条思路正确,却构造了远比答案复杂的巨大整数;固定宽度整数很快溢出,大整数的位数 和乘法成本也持续增长,而题目只问末尾的一小部分结构。 即使不保存整个阶乘,也可以逐个检查 ``1..n`` 中每个数含有多少因子 5,时间至少为 ``O(n)``。进阶要求提示我们继续压缩:无需访问每个数,只要按“5 的倍数”成批计数。 尾零为什么只需数因子 5 ~~~~~~~~~~~~~~~~~~~~~~~~ 每个十进制尾零来自一个因子 ``10 = 2 * 5``,所以尾零数量等于阶乘质因数分解中 2 和 5 指数的较小值。 在 ``1..n`` 中,2 的倍数比 5 的倍数多,4 的倍数也不少于 25 的倍数,依此类推: .. code-block:: text floor(n / 2^k) >= floor(n / 5^k) 把各层相加可知 ``n!`` 中因子 2 的总数不少于因子 5。每个因子 5 都能找到一个因子 2 配成 10,因此答案恰好是 ``n!`` 中因子 5 的总数。 为什么要分层计数 ~~~~~~~~~~~~~~~~ ``floor(n / 5)`` 只统计了每个 5 的倍数的第一个因子 5。像 25、50、75 这样的数还含有 第二个因子 5,125 及其倍数还含有第三个。完整计数为: .. code-block:: text floor(n / 5) + floor(n / 25) + floor(n / 125) + ... 第 ``k`` 层统计 ``5^k`` 的倍数,也就是至少含有 ``k`` 个因子 5 的数。若某个数恰好 含 ``t`` 个因子 5,它会在前 ``t`` 层各出现一次,正好贡献 ``t``,既不遗漏也不多算。 例如 ``n = 25`` 时,第一层 ``floor(25/5) = 5`` 统计 5、10、15、20、25 的首个因子; 第二层 ``floor(25/25) = 1`` 再统计 25 的第二个因子,答案为 6。只数 5 的倍数会错误地 得到 5。 连续整除压缩幂次 ~~~~~~~~~~~~~~~~ 可以显式令 ``power`` 依次取 ``5、25、125``,累加 ``n / power``;但不断执行 ``power *= 5`` 在扩大输入范围时需要额外防止乘法溢出。代码改为维护 ``remaining``: .. code-block:: text remaining = floor(remaining / 5) 完成第 ``k`` 次除法后,``remaining`` 恰为 ``floor(n / 5^k)``。这是因为连续整数除法 满足: .. code-block:: text floor(floor(n / 5^k) / 5) = floor(n / 5^(k+1)) 所以每轮先除以 5,再把结果加入答案,正好按顺序累加公式中的一层。状态变为 0 时,当前 层和所有更高层都为 0,可以停止。 状态走读 ~~~~~~~~ 对 ``n = 100``: .. code-block:: text 轮次 remaining 除以 5 后 累计答案 本层含义 1 20 20 5 的倍数 2 4 24 25 的倍数 3 0 24 更高层无贡献 ``100!`` 因而有 24 个尾零。对 ``n = 0`` 或 ``n < 5``,第一次或初始条件就使 ``remaining`` 为 0,没有任何因子 5,返回 0。 正确性与复杂度 ~~~~~~~~~~~~~~ 尾零数等于因子 5 总数;分层公式恰好统计每个整数含有的每一个因子 5;循环不变量又保证 代码逐项累加该公式,直到余下项全为 0。因此返回值就是 ``n!`` 的尾零数量。 ``remaining`` 每轮缩小为原来的五分之一,循环次数为 ``O(log_5 n)``,额外空间为 ``O(1)``。算法不计算阶乘、不创建大整数,也不显式构造 ``5^k``。