[LeetCode] 172. 阶乘后的零(Easy)C语言题解

1.题目相关

①题目及示例

Alt text

②相关标签

  • 数学

③题目地址


2.解题方法

①暴力解法(超时)

  • 思路:已知 2 * 5 = 10,所以尾数中零的数量只与 25 有关 。由此可知,我们只需要关注 N! 中作为乘法因子的 2 的数量和 5 的数量,最后计算 count(2) < count(5)? count(2): count(5) 即可。
  • 深入分析 1:2 的数量一定比 5 的数量多,所以只需要考虑 5 的数量(即统计小于或等于 N5 的倍数们能拆分成多少个 5)。

②数学规律

  • 深入分析 2:通过观察 5 的倍数(5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125 ……),可以发现对于 N! 的乘积因子来说,每隔 5 个数出现一个 5,每隔 25 个数出现两个 5,每隔 125 个数出现三个 5,以此类推,每隔 5^i 个数出现 i5,最终 5 的个数就是 N / 5 + N / 25 + N / 125 + ...
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

3.代码详解

①暴力解法(超时)

1
2
3
4
5
6
7
8
9
10
11
12
int trailingZeroes(int n){
int count = 0;
// 计算i的乘法因子中有几个5
for (int i = 5; i <= n; i += 5) {
int j = i;
while (j % 5 == 0) {
j /= 5;
count += 1;
}
}
return count;
}

②数学规律

1
2
3
4
5
6
7
8
int trailingZeroes(int n){
int count = 0;
while (n > 0) {
count += n / 5;
n /= 5;
}
return count;
}

附录

0%