# 172. 阶乘后的零




[原题](https://leetcode.cn/problems/factorial-trailing-zeroes/)

## 题目

![image-20220828112313399](https://cdn.jsdelivr.net/gh/GEAMING-CHN/images/blogimg/%E5%88%B7%E9%A2%98%E8%AE%B0%E5%BD%95/leetcode/172/image-20220828112313399.png)

## 思路

`n!`中有几个`0`与`[1,n]`中出现多少个5的因数有关。例如`7! = 1×2×3×4×5×6×7`出现了1次5，故最后末尾会出现1个0。`26!`中出现了`5,10,15,20,25`其中5的个数为`1+1+1+1+2=6`，故最后末尾会出现6个0。

## 解法

```c++
class Solution {
public:
    int cal(int k){
        if(k==0)
            return 0;
        else if(k%5==0){
            return cal(k/5)+1;
        }
        return 0;
    }
    int trailingZeroes(int n) {
        int count = 0;
        for (int i = 0;i<n+1;i+=5){
            count += cal(i);
        }
        return count;
    }
};
```

- 时间复杂度：$O(n)$，其中$n$为数组$nums$的长度，需要遍历一遍数组
- 空间复杂度：$O(1)$，仅使用常量空间

## 补充

![image-20220828115103279](https://cdn.jsdelivr.net/gh/GEAMING-CHN/images/blogimg/%E5%88%B7%E9%A2%98%E8%AE%B0%E5%BD%95/leetcode/172/image-20220828115103279.png)

所以可知：

$ans = n/5+n/5^2+n/5^3+\cdots$

```c++
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while (n) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
};
```

复杂度：

- 时间复杂度：$O(log\,n)$
- 空间复杂度：$O(1)$

[LeetCode] 172. 阶乘后的零