044 · Factorial Trailing Zeroes

algorithm

Published

June 23, 2026

My First Thoughts

嗯，这是求阶乘末尾的 0 有多少个。

首先就能想到，什么数字相乘会产生 0？

第一时间想到的就是：

2 × 5 = 10

也就是说，一个末尾的 0，本质上来自一组 2 和 5。

但在阶乘里，偶数很多，能提供因子 2 的数字也很多。所以真正稀缺的不是 2，而是 5。因此这题的关键其实就是：n! 里面一共有多少个因子 5。

我先看几个例子：

1 到 4 -> 0
5 -> 1
6 到 9 -> 1
10 -> 2
11 到 14 -> 2
15 -> 3

每遇到一个新的 5 的倍数，通常就会多一个因子 5，也就能和前面足够多的因子 2 配成一个新的 10。

所以第一层很容易想到：

n // 5

它表示 1..n 里面有多少个 5 的倍数。

而且容易想到，当出现5的幂次方时，需要加倍，因为可以拆分出多个5，也就是25、125 这些数。

比如：

25 = 5 × 5
50 = 2 × 5 × 5
125 = 5 × 5 × 5

它们不只是贡献一个因子 5。在 n // 5 里，它们已经被数过一次；但如果一个数是 25 的倍数，它还会额外多贡献一个因子 5。如果一个数是 125 的倍数，它又会再额外多贡献一个因子 5。

所以更清楚的说法是：

n // 5   数所有 5 的倍数，贡献第一层 5
n // 25  数所有 25 的倍数，补上第二层 5
n // 125 数所有 125 的倍数，补上第三层 5
...

也就是：

n // 5 + n // 25 + n // 125 + ...

直到除出来为 0，就说明后面没有更高层的 5 可以补了。

用循环写，可以每次把 n 除以 5：

total = 0

while n != 0:
    total += n // 5
    n = n // 5

return total

第一次加的是原始的 n // 5。第二次 n 已经变成了原始的 n // 5，所以再做 n // 5，等价于原始的 n // 25。第三次就等价于原始的 n // 125。

已经抓住重点并写出正确解法了。需要注意的细节是：不只是“25、125 这些幂次方要考虑”，它们的倍数也不能忽略，也就是50，75这些。

50 = 2 × 25 = 2 × 5 × 5

所以它也有两个因子 5。

因此这题更好的表达方式是：

每一层都在补数额外的因子 5。

n // 5 数第一层，n // 25 补第二层，n // 125 补第三层。这样就不会漏掉 50, 75, 100 这些 25 的倍数。

末尾的一个 0 来自一个因子 10：

10 = 2 × 5

在 n! 里面，因子 2 的数量一定不少于因子 5 的数量，所以答案等于 n! 中因子 5 的总数量。

数因子 5 时，分层统计：

n // 5   -> 每个 5 的倍数贡献一个 5
n // 25  -> 每个 25 的倍数额外贡献一个 5
n // 125 -> 每个 125 的倍数再额外贡献一个 5
...

循环里每次把 n 变成 n // 5，就自然进入下一层。

任何一个末尾的 0，都需要一个因子 10。

而：

10 = 2 × 5

所以问题可以转成：在 n! 的所有因子里，能配出多少组 2 × 5。

阶乘中偶数很多，因子 2 的数量比因子 5 多，所以真正限制答案的是因子 5 的数量。

接下来只要把每个数字中包含的因子 5 数出来：

因此：

total = n // 5 + n // 25 + n // 125 + ...

当下一层已经除到 0 时，说明后面没有更高次的 5 可以贡献了。

def trailingZeroes(n):
    total = 0

    while n != 0:
        total += n // 5
        n = n // 5

    return total

Time	\(O(\log_5 n)\) - 每次循环都把 `n` 除以 `5`
Space	\(O(1)\) - 只使用计数变量

遇到阶乘末尾 0，不要真的计算阶乘。先把 0 转成 10，再把 10 转成 2 × 5。因为阶乘里 2 足够多，所以问题就变成了分层统计因子 5：n // 5 + n // 25 + n // 125 + ...。