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

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

## 题目描述

```
给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

```

## 前置知识

- [递归](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md)

## 公司

- 阿里
- 腾讯
- 百度
- bloomberg

## 思路

我们需要求解这 n 个数字相乘的结果末尾有多少个 0，由于题目要求 log 的复杂度，因此暴力求解是不行的。

通过观察，我们发现如果想要结果末尾是 0，必须是分解质因数之后，2 和 5 相乘才行，同时因数分解之后发现 5 的个数远小于 2，
因此我们只需要求解这 n 数字分解质因数之后一共有多少个 5 即可.

![172.factorial-trailing-zeroes-2](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlubdkzp7j30i10970t2.jpg)

如图如果 n 为 30，那么结果应该是图中红色 5 的个数，即 7。

![172.factorial-trailing-zeroes-1](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlubf2c3fj30hr0b4aar.jpg)

我们的结果并不是直接 f(n) = n / 5, 比如 n 为 30， 25 中是有两个 5 的。
类似，n 为 150，会有 7 个这样的数字，通过观察我们发现规律`f(n) = n/5 + n/5^2 + n/5^3 + n/5^4 + n/5^5+..`

![172.factorial-trailing-zeroes-3](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlubgxccqj30h3091t9i.jpg)

如果可以发现上面的规律，用递归还是循环实现这个算式就看你的了。

## 关键点解析

- 数论

## 代码

- 语言支持：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:

```c++
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 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
