LeetCode 172中等数学
阶乘后的零 图解题解
这道题到底在问什么
给定整数 n,返回 n!(n 的阶乘)结果末尾连续 0 的个数。要求不真的算出 n!(它大到放不下)。
- n
- 25
- 25! 末尾
- 6 个 0
- n
- 100
- 100! 末尾
- 24 个 0
最优解：一步一步想明白
- 3每个末尾的 0,背后都藏着一对因子 2 和 5。问题就变成:n! 里 2 和 5 各有多少个?
- 42 多到用不完,5 才是稀缺资源。有几个 5,就能配几个 10,就有几个末尾 0。从此只数 5。
- 5把 5 的倍数挑出来把 1 到 25 里所有 5 的倍数挑出来(其它数不含因子 5)。下面逐个拆,看每个数里藏了几个 5。
- 65 → 一个 55 本身就是 5,含 1 个因子 5。累计 1 个。
- 710 → 一个 510 拆成 2×5,含 1 个 5。累计变 2。
- 815 → 一个 515 = 3×5,又 1 个 5。累计 3。
- 920 → 一个 520 = 4×5,再 1 个 5。累计 4。
- 1025 → 两个 5注意 25 = 5×5,它藏了 2 个因子 5!这一下累计跳到 6——这正是 25! 末尾有 6 个 0 的原因,也是这题的最大坑。
- 11像 25 含两个 5:它在 n÷5 里被数过一次,再在 n÷25 里被补数一次,正好两次。下面用这个公式把 n=100 完整走一遍。
- 12除数 d = 5下面这排是除数 d = 5 的各次幂。指针从 5 开始,每次算 100 ÷ d 加进答案,然后 d ×5 右移一格。
- 13d = 5指针落到第一个除数 5。先看循环条件:5 ≤ 100 成立,可以进循环开始累加。
- 14加 20100 ÷ 5 = 20(整数除法):1..100 里有 20 个数至少含一个 5。答案累加到 20。
- 15除数右移到 25把除数 ×5 变成 25,指针右移一格。25 还 ≤ 100,要继续——这一步专门补数那些「含两个 5」的数(25、50、75、100)。
- 16加 4100 ÷ 25 = 4:有 4 个数(25/50/75/100)含第二个 5,补上这 4 个。答案累加到 24。
- 17125 > 100,停除数再 ×5 变成 125,可 125 > 100 了,100 ÷ 125 = 0 没意义。后面的除数全用不上(变灰),循环停止。
- 18答案 = 24 ✓用到的两项(绿色):100÷5=20 和 100÷25=4,相加 24。这就是 100! 末尾零的个数,全程没碰那个天文数字。
- 19重置答案 ans = 0换回开头的 n = 25,答案归零重新开始,用公式再走一遍,看是否也得 6,和前面逐个拆的结果对上。
- 20d = 5指针回到除数 5。5 ≤ 25 成立,开始累加。
- 21加 525 ÷ 5 = 5:5,10,15,20,25 这 5 个数各至少一个 5。答案累加到 5。
- 22除数右移到 25除数 ×5 到 25,指针右移。25 ≤ 25 仍要算——这一步补数 25 里的第二个 5。
- 23加 125 ÷ 25 = 1:只有 25 这一个数含第二个 5,补上 1。答案 6——和前面逐个拆的结果完全一致!
- 24125 > 25,停除数到 125 已 > 25,停。最终 25! 末尾 6 个 0,公式法验证通过。
- 25记住这个公式:不断除以 5 的更高次幂并累加,本质就是把每个含多个 5 的数分层数清。
- 29n=25 只算 n/5 → 错得 5假如只除一次就返回,n=25 会得 5,漏掉 25 里第二个 5。必须继续除 25、125…把多层的 5 都补上才对。
⚠️ 容易写错的地方
✗ 错：以为答案 = n/5
✓ 对：要继续 + n/25 + n/125 + …
25=5×5、125=5×5×5 含多个 5,只除一次会漏数
✗ 错：d 用 int 一路 ×5
✓ 对：C++/Java 把 d 声明成 long
n 大时 d×5 会超过 int 上限溢出成负数,循环出错
✗ 错：去数因子 2
✓ 对：只数因子 5
2 远多于 5,配对受 5 限制,数 2 是白费功
完整代码（Python / C++ / Java）
Python
class Solution:
def trailingZeroes(self, n):
count = 0
d = 5
while d <= n: # 除数没超过 n 就继续
count += n // d # 加上这一层的 5 的个数
d *= 5 # 除数升到下一个 5 的幂
return countC++
class Solution {
public:
int trailingZeroes(int n) {
int count = 0;
for (long d = 5; d <= n; d *= 5) { // long 防溢出
count += n / d;
}
return count;
}
};Java
class Solution {
public int trailingZeroes(int n) {
int count = 0;
for (long d = 5; d <= n; d *= 5) { // long 防溢出
count += n / d;
}
return count;
}
}复杂度
时间复杂度
O(log n)
除数每轮 ×5,从 5 涨到超过 n 只需 log₅n 步,所以循环次数是 log 级
空间复杂度
O(1)
只用 count 和 d 两个变量,不开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 阶乘后的零 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么末尾 0 的个数等于因子 5 的个数?+
末尾每个 0 由一个 10=2×5 产生。阶乘里因子 2 远多于 5,能凑的 (2,5) 对数被较少的 5 限制,所以等于 5 的个数。
为什么要继续除 25、125?+
25=5²、125=5³ 这类数含多个 5。n/5 只把每个数数一次,n/25 给含两个 5 的再补一次,以此类推,分层数全。
为什么是 O(log n)?+
除数 d 每轮乘 5,呈指数增长,从 5 到超过 n 只需 log₅n 步,循环次数是对数级。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 阶乘后的零 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。