给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes
AC代码
class Solution {
/**
* 思路
* 任意两个数相乘，都可以转化为质数相乘的形式，比如4*6=(2^3)*3，n!也一样可以转化为质数相乘的形式
* 质数中，只有2*5会产生0，而2的数量一定比5多（每5个数有两个2，一个5），所以本题的结果，其实就是n!中含因子5的数量
* 设最终结果为result
* 假设1到n中，共有k1个5^1的倍数，5^1至少含1个因子5，result += k1
* 假设1到n中，共有k2个5^2的倍数，5^2至少含2个因子5，但是其中1个上一步已经算过了，所以新增的因子5的数量只有k2，result += k2
* 假设1到n中，共有k3个5^3的倍数，5^3至少含3个因子5，但是其中2个上一步已经算过了，所以新增的因子5的数量只有k3，result += k3
* 依此类推
* @param n
* @return
*/
public int trailingZeroes(int n) {
int result = 0;
// multiple是5的倍数
for (long multiple = 5; multiple <= n; multiple *= 5) {
result += n / multiple;
}
return result;
}
}
image.png
