172. 阶乘后的零题解
题目来源：172. 阶乘后的零
2022.03.25 每日一题
LeetCode 题解持续更新中Github仓库地址 CSDN博客地址
今天的题目比较简单，想明白就好了
首先我们要分析一下，什么时候会出现 0
那就是出现 2 和 5 的时候会出现 0
那么问题就转变成为，n!之中 包含多少的2和 5，然后取两者的最小值即可
那么如何找到n!之中 包含多少的2和 5呢？
首先，广泛一点，对于一个数组 n，其中 可以 分解出 p 的个数是多少
- 至少能分解出 p 的个数有 (int) n/p 个
- 至少能分解出
p
2
p^2
p2 的个数有 (int)n
/
p
2
n/p^2
n/p2 个 - 至少能分解出
p
3
p^3
p3 的个数有 (int)n
/
p
3
n/p^3
n/p3 个 - 至少能分解出
p
k
p^k
pk 的个数有 (int)n
/
p
k
n/p^k
n/pk 个
其中上述每一个类，都是类的上一个类的子集，
因此本题中 2 的个数就是 (int)
n
/
2
+
n
/
2
2
+
n
/
2
3
+
n
/
2
4
+
…
…
+
n
/
2
k
n/2+n/2^2+n/2^3+n/2^4+……+n/2^k
n/2+n/22+n/23+n/24+……+n/2k
同理 5 的个数就是 (int)
n
/
5
+
n
/
5
2
+
n
/
5
3
+
n
/
5
4
+
…
…
+
n
/
5
k
n/5+n/5^2+n/5^3+n/5^4+……+n/5^k
n/5+n/52+n/53+n/54+……+n/5k
我们可以知道 5 的数量是小于 2 的数量的，因此，直接统计 5 的数量即可
class Solution {
public:
int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
};
public class Solution {
public int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + tt(n / 5);
}
}