阶乘后的零最优解：从暴力计算到质因子5的O(log n)算法

第一次看到阶乘后的零这个题很多人第一反应是这还不简单把 n! 算出来再数一数末尾有几个 0 不就行了等真动手写代码才发现这个思路有两个坎一是数字大一点就溢出二是就算用上大数运算算出来的东西也基本不可用。这个题在 LeetCode 上是第 172 题看起来只是一个简单中等难度的数学题但它背后藏着一整套从暴力到最优的演化逻辑面试时也经常被拿来考察候选人的数学直觉和复杂度分析能力。这篇文章我准备从最笨的写法开始一直推到最优解把每一步的动机和选择都拆开讲清楚。不管你是刚开始刷题的新手还是准备面试想复习数学题的选手都能从这套递进思路里拿到一些能直接用的东西。1. 最直接的暴力思路先算阶乘再数零1.1 暴力计算的实现与致命瓶颈先说大多数人第一眼想到的方案写一个循环把 n! 算出来然后不断对 10 取余统计末尾连续的 0 的个数。题目的例子很简单n 3 时 3! 6末尾没零n 5 时 5! 120末尾一个零n 10 时 10! 3628800末尾两个零。小数字看着完全没问题代码也不复杂def trailing_zeroes_v1(n: int) - int: # 先算阶乘再数末尾零仅用于理解暴力逻辑 fact 1 for i in range(2, n 1): fact * i count 0 while fact % 10 0: count 1 fact // 10 return count这段代码在 n 5、n 10 的时候都能得出正确答案但它的瓶颈太明显了阶乘的增长速度是指数级别的准确说是比任何多项式增长都快。n 20 时20! 已经是 2432902008176640000约 2.4 × 10^18已经超过了多数编程语言里 64 位整数的表示范围n 再大一点64 位也不够用。1.2 溢出这堵墙整数表示与阶乘爆炸这里我想多说一句溢出问题因为它不是这道题独有的坑。大部分语言里int 是 32 位最大值约 21 亿long 是 64 位最大值约 9.2 × 10^18。可阶乘增长实在太快了n 21 时 21! 就已经超过 64 位整数范围。也就是说暴力法连 n 21 都扛不住更别提题目里可能出现的大 n。有些朋友会说我用 Python整数没上限不就不会溢出吗对Python 的大整数确实能算更大的 n可代价也很现实。算 n! 本身会产生一个超长整数它的位数大概是 n log n 量级。如果 n 是十万这个数字就有几十万位如果 n 是一百万就有几百万位。为了数末尾的零你白白生成了一个庞大无比的数字时间和内存全都耗在了一个正要丢弃的东西上。哪怕不溢出这也是一条死胡同。1.3 从暴力结果中归纳出的规律线索暴力方案虽然不能用于大 n但它有个意外的价值它会帮我们积累数据直觉。把 n 从 1 到 30 的答案列出来能看到一些规律nn!末尾零个数5120110362880021513076743680003202432902008176640000425155112100433309859840000006302652528598121910586363084800000007注意这里最明显的变化答案是每隔几个数跳一次不是 n 每增加 1 就稳定加 1。尤其是 n 从 24 到 25 的时候末尾零从 4 个直接跳到 6 个一次多了 2 个。暴力结果看多了你会想问一个问题末尾的零到底是从哪来的答案不是从天上掉下来的它一定来自乘积中制造出 10的因子。2. 10 的因子才是零的真正来源数学建模2.1 10 2 × 5为什么 5 才是稀缺资源阶乘是连续整数的乘积n! 1 × 2 × 3 × … × n。十进制里一个数末尾有一个 0意味着这个数一定包含一个因子 10。而 10 2 × 5所以某个数末尾有几个 0就等于它里面有多少个 2 × 5 组合。关键来了在从 1 到 n 的所有数里因子 2 和因子 5 出现的频率完全不一样。每两个数里就有一个包含因子 2每五个数里才有一个包含因子 5。如果统计 n! 里因子 2 的个数和因子 5 的个数会发现 2 的个数永远比 5 多而且多得多。比如 n 10 时10! 1×2×3×4×5×6×7×8×9×10数一数因子 22、4、6、8、10 分别贡献不少总数大概是 8 个而因子 5 呢只有 5 和 10 各贡献一个总共 2 个。要组成 10就用 2 个 2 去搭配 2 个 5剩下的 2 都用不上。所以零的个数本质上不取决于 2而取决于 5。2 是无限的5 才是稀缺方。这就像装礼盒盒子的封条要求一个 2 配一个 5你有大量 2但 5 总共就那几个能装多少盒完全看 5 的数量。2.2 每个 5 至少配得上一个 2稀缺性论证有人可能会担心万一某个数特别奇葩因子 5 太多、因子 2 不够那数 5就不准了。这种担心在数学上是合理的但在这个题里完全不成立。因为 1 到 n 的连续序列里因子 2 的数量始终领先。可以做个严谨但简单的估计1 到 n 中能被 2 整除的数至少有 n/2 个能被 4 整除的有 n/4 个能被 8 整除的有 n/8 个……所以因子 2 的总数大约是 n/2 n/4 n/8 …约等于 n 个。而因子 5 的总数大约是 n/5 n/25 n/125 …约等于 n/4 个。在 n 足够大的时候2 的个数远大于 5。从最小的情况核对n 5 时因子 2 有 3 个因子 5 有 1 个供求关系已经满足n 1 或 n 2 时因子 5 本身就是 0答案也是 0。所以在全部有效输入上每个 5 都能找到配套的 2这个前提都成立。2.3 零的个数等于因子 5 的个数初步结论现在可以把问题翻译成更精确的形式n! 末尾零的个数 n! 中质因子 5 的总个数。这不是巧合也不是近似而是精确等式。理解了这一步题目的复杂度立刻从算一个大数变成了数一数因数里有多少个 5。接下来就只差一件事怎么又快又准地统计从 1 到 n 的乘积里到底有多少个质因子 5。3. 质因数分解视角直接数 n! 里有多少个 53.1 整除 5、25、125……的逐层计数法数 n! 中的因子 5不能只数一遍 5 的倍数因为 25 里有两个 5125 里有三个 5这些会漏掉。正确的做法是靠逐层整除。先把 1 到 n 里能被 5 整除的数都贡献一个 5得到第一层这些数是 5、10、15、…总共有 n/5 个。接着能再被 25 整除的数会在刚才的基础上多贡献一个 5数量是 n/25 个。再接着能被 125 整除的数再多贡献一个 5数量是 n/125 个。把每一层的贡献加起来就是完整的因子 5 个数count n/5 n/25 n/125 ...这里每一项都向下取整。为什么是对的可以换个角度理解一个数如果等于 25 5^2它在除以 5这一层被统计了一次在除以 25这一层又被统计了一次总共计入 2 次刚好等于它包含的两个 5。125 5^3 会被统计 3 次依次类推。每一层枚举的是把全部因子 5 分成一层层来看。3.2 公式推导与循环实现写代码就很简单了核心是把n 循环除以 5 并累加这个动作写清楚def trailing_zeroes(n: int) - int: count 0 while n 0: n // 5 count n return count这段代码的精妙之处在于它把 n/5 n/25 n/125 … 这个无限求和变成了一根循环。因为每次把 n 整除 5 以后下一轮 sum 里实际统计的就是原来 n/25 那一层。循环条件是 n 0当 n 变成 0 时所有更大幂次的贡献都为 0循环自然停止。用 JavaScript 写也同样直观var trailingZeroes function (n) { let count 0; while (n 0) { n Math.floor(n / 5); count n; } return count; };3.3 复杂度分析与边界情况这个循环每轮把 n 至少缩小 5 倍所以总次数是 log₅n 级别的。对于 int 范围内的任意 n循环最多跑十几轮。时间复杂度 O(log n)空间复杂度 O(1)。相比暴力法的阶乘计算这个方案既没算阶乘也没碰大数从根本上绕开了溢出问题。边界情况也要检查一下n 0 时0! 1末尾零个数是 0循环不执行直接返回 0正确。n 1 到 4 时答案都是 0也正确。n 25 时n/5 5n/25 1合计 6这和我在前面表格里看到的暴力结果完全一致。4. 从递推回到直觉代码还可以怎么写4.1 两种等价实现循环累加与递归上面的循环写法已经是最常见的标准答案。不过面试时有些面试官会追问能不能用递归写可以。递归式很漂亮def trailing_zeroes(n: int) - int: if n 0: return 0 return n // 5 trailing_zeroes(n // 5)这其实就是把 f(n) n/5 f(n/5) 直接翻译过来。递归终止条件是 n 变成 0。理论上它和循环完全等价但需要注意递归深度只有 log₅n大概十几层不会触发栈溢出。我个人在面试时会更推荐循环版本因为它更贴近逐层累加的直觉不需要额外解释函数调用栈。但如果面试官想看你对递归的理解能流畅写出递归版本会是加分项。4.2 时间复杂度的细节为什么是 O(log n)很多人会问为什么不是 O(log₅n) 而写成 O(log n)这就要说到复杂度记号的惯例了对数的底数在渐进意义下只是常数倍关系。log₅n 和 log₁₀n 之间相差一个常数因子 2 点多所以统一写 O(log n) 就够精确了。真正重要的是n 翻倍时循环次数只增加一个常数这个增长太慢了。对任何 32 位整数来说最多循环约 15 次即使换到 64 位整数也只要约 28 次。这是教科书级的每次规模缩小固定倍数复杂度模型。4.3 代码模板与可读性讨论如果看了很多题解你会发现几乎所有语言的写法都长一个样除到不能再除然后累加。这个模板很短但有一点我希望大家注意除法的写法一定要小心不同语言对整数除法的语义有差别。Python 里n // 5是地板除法负数和正数都向下取整写起来干净。JavaScript 里没有原生整数除法必须写Math.floor(n / 5)记忆负担稍大。Java 里n / 5本身就是整数除法不用额外处理。这些语言差异在刷题时可以忽略但一旦到了现场写代码的环境往往就是这些小差异让你多调两分钟 bug。可读性方面还有一个建议函数命名尽量用trailingZeroes参数名用n不要写在循环里临时造一堆变量。这道题的解法太短代码风格好坏一眼就能看出来。5. 面试场景下的变形与易错点5.1 变形题不数 n!而是数乘积、组合数、某进制这道题之所以常被面试官重用是因为它太容易变形了。最常见的几种给出一个区间的乘积比如 [m, n] 范围内所有整数相乘末尾零有几个答案直接用 f(n) - f(m - 1) 就行本质还是数因子 5。数组合数 C(n, k) 的末尾零。这个稍微复杂组合数 分子阶乘除以两个分母阶乘。需要分别算出分子和分母中 2 与 5 的个数再取 min(总因子 2 数, 总因子 5 数)。因为分母会消掉一部分因子。数从 1 到 n 的奇数乘积的末尾零。奇数序列里一个 2 都没有所以答案恒为 0。很多人会下意识套公式结果算出一堆数但原理一推就露馅。问 n! 在 m 进制下的末尾零。这时要把 m 做质因数分解然后分别统计每个质因子在 n! 里的个数再用总个数除以该质因子在 m 中的指数取最小值。比如 12 2² × 3既要数 2 又要数 3答案要兼顾两项。理解了零取决于进制因子这个本质变来变去都不怕。5.2 易错点一误以为答案是 n 里 5 的倍数个数最常见的错误是看到答案公式写成 n/5 n/25 …然后心里想前面那项已经很大了是不是 n/25 不用加了或者只写了n // 5就返回。这两种都会在 n 达到 25 的倍数时翻车。为什么必须加 n/25因为一个数如果含有 25 这个因子它本身就代表两个 5。第一层除以 5 只计入了一个 5第二个 5 必须由 n/25 补上。可以动手验算n 25只算 n/5 5但真实答案 6差就差在 25 本身多出的那个 5 上。还有更隐蔽的情况n 125 时只算前两层合计 25 5 30但真实答案是 31第三个 5 来自 125 本身。所以循环必须一直除到 n 变成 0一个层级都不能省。5.3 易错点二边界输入与无符号陷阱题目一般不讨论负数但面试时你最好主动提一句如果 n 0阶乘本身在经典定义里不成立可以直接返回 0 或抛异常看题目约定即可。这个细节看起来没用却能展示你对输入域的思考。另一个被忽视的边界是 n 0。0! 定义为 1末尾零为 0循环不会执行返回 0代码天然正确。但如果你用递归写法终止条件漏掉 n 0就会导致无穷递归或者错误结果。刷题时不要因为用例简单就跳过这些边角现场跑测试的时候它们最容易暴露问题。5.4 面试官的追问如果改成基数不是 10 怎么办这是把这题推向纵深的最佳问题。面试官可能会问如果要求 n! 在二进制表示末尾有几个 0答案其实更简单二进制的零对应因子 2所以答案等于 n! 里因子 2 的个数公式是 n/2 n/4 n/8 …。如果问的是八进制8 2³答案就是因子 2 的个数除以 3 向下取整。如果问的是十六进制16 2⁴答案是因子 2 的个数除以 4 向下取整。你不需要背下每种进制的答案只需要记住一个万能流程先对进制做质因数分解再统计 n! 中各个质因子的个数最后看哪个质因子最稀少它决定了能凑出多少个进制单位。这个过程一旦讲清楚面试官基本就能确认你是真的理解了而不是背了公式。说到最后我额外分享一个自己刷题时的小习惯做完这道题后我会拿一个比较大的 n比如 1000000用最优解跑一遍看看结果是否符合每 5 个数进一位、每 25 个数多进一位、每 125 个数再多进一位的直觉。这比单纯背代码更能加深理解。后面遇到任何跟因子、后缀零相关的题我都会先问自己一句这些零在目标进制里到底对应什么因子需求方是 2 还是 5想清楚这个代码怎么写都是顺水推舟的事。