# 0172. 阶乘后的零
### 题目地址(172. 阶乘后的零)
### 题目描述
```
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
```
### 前置知识
* [递归](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/basic-data-structure)
### 公司
* 阿里
* 腾讯
* 百度
* bloomberg
### 思路
我们需要求解这 n 个数字相乘的结果末尾有多少个 0，由于题目要求 log 的复杂度，因此 暴力求解是不行的。
通过观察，我们发现如果想要结果末尾是 0，必须是分解质因数之后，2 和 5 相乘才行， 同时因数分解之后发现 5 的个数远小于 2，因此我们只需要求解这 n 数字分解质因数之后 一共有多少个 5 即可.
如图如果 n 为 30，那么结果应该是图中红色 5 的个数，即 7。
我们的结果并不是直接 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+..`
如果可以发现上面的方程，用递归还是循环实现这个算式就看你的了。
### 关键点解析
* 数论
### 代码
* 语言支持：JS，Python，C++, Java
Javascript Code:
```js
/*
* @lc app=leetcode id=172 lang=javascript
*
* [172] Factorial Trailing Zeroes
*/
/**
* @param {number} n
* @return {number}
*/
var trailingZeroes = function (n) {
// tag: 数论
// if (n === 0) return n;
// 递归： f(n) = n / 5 + f(n / 5)
// return Math.floor(n / 5) + trailingZeroes(Math.floor(n / 5));
let count = 0;
while (n >= 5) {
count += Math.floor(n / 5);
n = Math.floor(n / 5);
}
return count;
};
```
Python Code:
```python
class Solution:
def trailingZeroes(self, n: int) -> int:
count = 0
while n >= 5:
n = n // 5
count += n
return count
# 递归
class Solution:
def trailingZeroes(self, n: int) -> int:
if n == 0: return 0
return n // 5 + self.trailingZeroes(n // 5)
```
C++ Code:
```
class Solution {
public:
int trailingZeroes(int n) {
int res = 0;
while(n >= 5)
{
n/=5;
res += n;
}
return res;
}
};
```
Java Code:
```js
class Solution {
public int trailingZeroes(int n) {
int res = 0;
while(n >= 5)
{
n/=5;
res += n;
}
return res;
}
}
```
**复杂度分析**
* 时间复杂度：$O(logN)$
* 空间复杂度：$O(1)$
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你 识别套路，高效刷题。
