172.阶乘后的0.md

172.阶乘后的0

题目

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

示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

方法

如果计算出阶乘后再统计尾数中0的数量的话，当n很大时计算阶乘的过程肯定会溢出。因此需要考虑其他方法

题目要求的是结果中尾数为0的数量，其他的0不用管。分析可知，只有乘10才会在一个数的尾数中添一个0。而10只能分解成2和5两个因子，因此在计算阶乘的过程中每出现的一对2 * 5都会在结尾贡献一个0。

进一步分析，每一个偶数都有一个因子2，每一个5的倍数都有一个因子5。在所有小于n的数中，偶数的个数肯定多于5的倍数的个数，因此因子2出现的次数肯定比因子5出现的次数多，而且必须2和5结合在一起才能凑成一个10。因此，要统计在计算阶乘的过程中乘过多少10，只需要统计乘过多少5即可（因为2出现的次数足够多）。

在小于n的数中，每一个5的倍数都会贡献5。其中：

• 在5-25之间的5的倍数会贡献1个5
• 在25-125之间的5的倍数会贡献2个5
• 在125-625之间的5的倍数会贡献3个5
• 依次类推

public int trailingZeroes(int n) {
    if(n <= 4)
        return 0;
    int res = 0;
    while(n > 0){
        res += (n / 5);
        n = n / 5;
    }
    return res;
}