172. 阶乘后的零

题目

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

提示 n! = n (n - 1) (n - 2) … 3 2 1

示例 1：

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

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

输入：n = 0
输出：0

提示：

0 <= n <= 10^4

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

思路

阶乘因子中，的来源都可以拆成和的乘积，比如，和不是质因子，而和是，那么我们统计和的数目就好了。而由于的数目一定不少于，所以统计的数目就好了。即统计到中每个数最多可以拆出多少个。

首先，每隔一个会出现的倍数，每个数含个，总共贡献个。每隔会出现一个的倍数，每个数含再贡献一个，又多贡献个。以此类推，这个间隔最大是小于的最大的的次方数。

举个例子，为，从开始，每隔出现一个的倍数，总共出现个。从开始，每隔出现一个的倍数，再多贡献个，一共出现个。也就是有个。

代码

class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        for (int i = 1; (int) Math.pow(5, i) <= n; i++) {
            ans += n / (int) Math.pow(5, i);
        }
        return ans;
    }
}