172. 阶乘后的零
题目描述
给定一个整数 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
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
解法
方法一：数学
题目实际上是求 $[1,n]$ 中有多少个 $5$ 的因数。
我们以 $130$ 为例来分析：
第 $1$ 次除以 $5$，得到 $26$，表示存在 $26$ 个包含因数 $5$ 的数；
第 $2$ 次除以 $5$，得到 $5$，表示存在 $5$ 个包含因数 $5^2$ 的数；
第 $3$ 次除以 $5$，得到 $1$，表示存在 $1$ 个包含因数 $5^3$ 的数；
累加得到从 $[1,n]$ 中所有 $5$ 的因数的个数。
时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。
Python3
class Solution:
def trailingZeroes(self, n: int) -> int:
ans = 0
while n:
n //= 5
ans += n
return ans
Java
class Solution {
public int trailingZeroes(int n) {
int ans = 0;
while (n > 0) {
n /= 5;
ans += n;
}
return ans;
}
}
C++
class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
while (n) {
n /= 5;
ans += n;
}
return ans;
}
};
Go
func trailingZeroes(n int) int {
ans := 0
for n > 0 {
n /= 5
ans += n
}
return ans
}
TypeScript
function trailingZeroes(n: number): number {
let ans = 0;
while (n > 0) {
n = Math.floor(n / 5);
ans += n;
}
return ans;
}