0172. Factorial Trailing Zeroes

题目信息

题号:
  1. 阶乘后的零

难度:

Medium

主题:

数学、质因数计数、整除

原题:

LeetCode 0172

重点:

把巨大阶乘的末尾结构转化为因子 5 的分层计数,并用连续整除避免幂次溢出

题目重述

给定非负整数 n,返回 n! 的十进制表示末尾连续零的数量。

0! = 1,所以 n = 0 时答案为 0。进阶要求在优于 O(n) 的时间内完成。

自建示例

输入:n = 5
输出:1

5! = 120,末尾有一个零。
输入:n = 25
输出:6

5、10、15、20 各贡献一个因子 5,25 = 5² 额外再贡献一个,共 6 个。
输入:n = 3
输出:0

3! = 6,没有因子 10。

C++ 实现

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 的倍数,依此类推:

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 及其倍数还含有第三个。完整计数为:

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:

remaining = floor(remaining / 5)

完成第 k 次除法后,remaining 恰为 floor(n / 5^k)。这是因为连续整数除法 满足:

floor(floor(n / 5^k) / 5) = floor(n / 5^(k+1))

所以每轮先除以 5,再把结果加入答案,正好按顺序累加公式中的一层。状态变为 0 时,当前 层和所有更高层都为 0,可以停止。

状态走读

对 n = 100:

轮次  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。