0172. 阶乘后的零

题目地址(172. 阶乘后的零)

https://leetcode-cn.com/problems/factorial-trailing-zeroes/

题目描述

1
给定一个整数 n,返回 n! 结果尾数中零的数量。
2
3
示例 1:
4
5
输入: 3
6
输出: 0
7
解释: 3! = 6, 尾数中没有零。
8
示例 2:
9
10
输入: 5
11
输出: 1
12
解释: 5! = 120, 尾数中有 1 个零.
13
说明: 你算法的时间复杂度应为 O(log n) 。
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • bloomberg

思路

我们需要求解这 n 个数字相乘的结果末尾有多少个 0,由于题目要求 log 的复杂度,因此 暴力求解是不行的。
通过观察,我们发现如果想要结果末尾是 0,必须是分解质因数之后,2 和 5 相乘才行, 同时因数分解之后发现 5 的个数远小于 2,因此我们只需要求解这 n 数字分解质因数之后 一共有多少个 5 即可.
172.factorial-trailing-zeroes-2
如图如果 n 为 30,那么结果应该是图中红色 5 的个数,即 7。
172.factorial-trailing-zeroes-1
我们的结果并不是直接 f(n) = n / 5, 比如 n 为 30, 25 中是有两个 5 的。类似,n 为 150,会有 7 个这样的数字。
其中 f(n) = n / 5 其实仅表示分解出的质因数仅包含一个 5 的个数。而我们的答案是质 因数中所有的 5 。因此等价于 f(n) = n / 5 + n / 25 + n / 125 + ... + n / 5^k
5 ^ k 表示 质因数中有 k 个 5 的个数
据此得出转移方程:f(n) = n/5 + n/5^2 + n/5^3 + n/5^4 + n/5^5+..
172.factorial-trailing-zeroes-3
如果可以发现上面的方程,用递归还是循环实现这个算式就看你的了。

关键点解析

  • 数论

代码

  • 语言支持:JS,Python,C++, Java
Javascript Code:
1
/*
2
* @lc app=leetcode id=172 lang=javascript
3
*
4
* [172] Factorial Trailing Zeroes
5
*/
6
/**
7
* @param {number} n
8
* @return {number}
9
*/
10
var trailingZeroes = function (n) {
11
// tag: 数论
12
13
// if (n === 0) return n;
14
15
// 递归: f(n) = n / 5 + f(n / 5)
16
// return Math.floor(n / 5) + trailingZeroes(Math.floor(n / 5));
17
let count = 0;
18
while (n >= 5) {
19
count += Math.floor(n / 5);
20
n = Math.floor(n / 5);
21
}
22
return count;
23
};
Copied!
Python Code:
1
class Solution:
2
def trailingZeroes(self, n: int) -> int:
3
count = 0
4
while n >= 5:
5
n = n // 5
6
count += n
7
return count
8
9
10
# 递归
11
class Solution:
12
def trailingZeroes(self, n: int) -> int:
13
if n == 0: return 0
14
return n // 5 + self.trailingZeroes(n // 5)
Copied!
C++ Code:
1
class Solution {
2
public:
3
int trailingZeroes(int n) {
4
int res = 0;
5
while(n >= 5)
6
{
7
n/=5;
8
res += n;
9
}
10
return res;
11
}
12
};
Copied!
Java Code:
1
class Solution {
2
public int trailingZeroes(int n) {
3
int res = 0;
4
while(n >= 5)
5
{
6
n/=5;
7
res += n;
8
}
9
return res;
10
}
11
}
Copied!
复杂度分析
  • 时间复杂度:$O(logN)$
  • 空间复杂度:$O(1)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你 识别套路,高效刷题。