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

提示 $n!=n\ast (n-1)\ast (n-2)\ast ...\ast 3\ast 2\ast 1$

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0

提示：

$0<=n<=10^4$

进阶： 你可以设计并实现对数时间复杂度的算法来解决此问题吗？

---

暴力枚举：

可以发现在乘的过程中，末尾 0 的个数总是增加的，所以可以考虑每乘一次，就将对应的末尾 0 计数，然后消除掉末尾 0，这样可以防止溢出
比如：120 * 5 = (12 * 5)0 = 600

优化：看代码，利用 10 的倍数取余，防止溢出，并且使得末尾 0 的个数不变
比如：$x=13859448592385$，但是后面的乘积是否有0，和末尾的最后几位数有关，可以只取最后几位

时间复杂度：$O(NlogN)$
空间复杂度：$O(1)$

class Solution {
public:int trailingZeroes(int n) {unsigned long long x = 1;long long res = 0;for(int i = 1; i <= n; i++){x *= i;if(x > 1000000) x = x % 1000000;while(x % 10 == 0) res++, x /= 10;}return res;}
};

利用数学知识推导：

$1\ast 2\ast 3\ast \mathrm{4...}\ast n$ 的乘积，能产生末尾0的只有 $(2或2的倍数\ast 5或5的倍数)$ 可以，所以只需要找到乘积里面有多少对$(2\ast 5)$，并且 $2的倍数$ 的个数肯定是 多于 $5的倍数$，所以只需要找乘积里有多少个 5 即可
$1\ast 2\ast 3\ast \mathrm{4...}\ast n=1\ast 2\ast ..(1\ast 5)..(2\ast 5)..(3\ast 5)...(\mathrm{4..5})...(5\ast 5)....(5\ast 5\ast 5)...$，像 $5\ast 5$ 其实是可以贡献 两个5 的（即贡献两个末尾0），所以只需要对 5 的倍数，计算出每个 5 的倍数能贡献几个 5，求出总和，就是 末尾0 的个数

时间复杂度：$O(NlogN)$
空间复杂度：$O(1)$

class Solution {
public:int trailingZeroes(int n) {long long res = 0;for(int i = 5; i <= n; i+=5){int x = i;while(x % 5 == 0) res++, x /= 5;}return res;}
};