Factorial Trailing Zeroes
最后更新于：2022-04-01 22:56:16
## 一.题目描述
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
## 二.题目分析
题目的要求是，给定一个整数`n`，找出`n!`结果的末尾为`0`的数的个数。暴力法是首先求出`n!`，然后直接计算末尾`0`的个数。（重复(n!)/10，直到余数非0为止），若输入的`n` 值过大时，在计算阶乘时会导致溢出，因此该方法并不好用。
[http://www.cnblogs.com/ganganloveu/p/4193373.html](http://www.cnblogs.com/ganganloveu/p/4193373.html) 给出一种很巧妙的解决方法：
事实上，只要对`n`的阶乘`n!`，做因数分解：`n!=2^x*3^y*5^z*...`
显然`0`的个数等于`min(x,z)`，并且经证明，可以得到：`min(x,z)==z` 。
例如：
`n = 5`时，`5!`的质因数分解：`5! = 2 * 2 * 2 * 3 * 5` 中包含`3`个`2`、`1`个`3`和`1`个`2`。后缀`0`的个数是`1`。
`n = 11`时，`11!`的质因数分解：`11! = 2^8 * 3^4 * 5^2 * 7` 中包含`8`个`2`、`4`个`3`和`2`个`5`。后缀`0`的个数是`2`。
证明：
对于阶乘而言，也就是`1*2*3*...*n`，设`[n/k]`代表`1~n`中能被k整除的个数
显然有，`[n/2] > [n/5]` (左边是逢`2`增`1`，右边是逢`5`增`1`)
`[n/2^2] > [n/5^2]`(左边是逢`4`增`1`，右边是逢`25`增`1`)
……
`[n/2^p] > [n/5^p]`(左边是逢`2^p`增`1`，右边是逢`5^p`增`1`)
随着幂次`p`的上升，出现`2^p`的概率会远大于出现`5^p`的概率。
因此左边的加和一定大于右边的加和，也就是`n!`质因数分解中，`2`的次幂一定大于`5`的次幂。
## 三.示例代码
~~~
#include
using namespace std;
class Solution{
public:
int trailingZeroes(int n) {
int result = 0;
while (n)
{
result += n / 5;
n /= 5;
}
return result;
}
};
~~~
## 四.小结
这道题的代码很少，但是要从题目中把复杂的要求转化为简单的运算是需要推导的，总体来说还是需要费一定的功夫。
';