LeetCode 题解工作台
阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1 示例 1： 输入： n = 3 输出： 0 解释： 3! = 6 ，不含尾随 0 示例 2： 输入： n = 5 输出： 1 解释： 5! = 120…
1
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数学·driven
答案摘要
题目实际上是求 中有多少个 的因数。 我们以 为例来分析：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3 输出：0 解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5 输出：1 解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0 输出：0
提示：
0 <= n <= 104
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
解题思路
方法一：数学
题目实际上是求 中有多少个 的因数。
我们以 为例来分析：
- 第 次除以 ，得到 ，表示存在 个包含因数 的数；
- 第 次除以 ，得到 ，表示存在 个包含因数 的数；
- 第 次除以 ，得到 ，表示存在 个包含因数 的数；
- 累加得到从 中所有 的因数的个数。
时间复杂度 ，空间复杂度 。
class Solution:
def trailingZeroes(self, n: int) -> int:
ans = 0
while n:
n //= 5
ans += n
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates an understanding of the mathematical properties of factorials.
- question_mark
The candidate can implement an efficient solution without calculating the entire factorial.
- question_mark
The candidate effectively handles edge cases such as n = 0.
常见陷阱
外企场景- error
Brute force methods that attempt to calculate n! directly will fail for large values of n due to factorial growth.
- error
Overlooking powers of 5 beyond the first (e.g., missing multiples of 25, 125).
- error
Incorrect handling of n = 0, which should return 0 trailing zeroes.
进阶变体
外企场景- arrow_right_alt
Extend the problem to find trailing zeroes in large factorials where n exceeds typical data types.
- arrow_right_alt
Modify the problem to count trailing zeroes in base b factorials instead of base 10.
- arrow_right_alt
Optimize the approach further for very large n to minimize computational time.