leetCode-172:Factorial Trailing Zeroes

问题描述

给定一个整数 n，要求找出 n! 的值末尾右多少个 0，题目链接：点我

样例输入输出

输入：5

输出：1

解释：5! = 5 * 4 * 3 * 2 * 1 = 120，末尾有一个0

输入：2

输出：0

问题解放

此题简单的做法按阶乘做法进行计算，中间数字如果末尾是0，则除10并计数加一，为了相乘的结果不溢出，中间需要进行模100的操作。但是这样的时间复杂度是 O(n)。可以进一步优化。

观察阶乘算法过程，我们可以知道，末尾的 0 是由 2 和 5 （包括 2 和 5 的倍数）产生的，因此只需要找到 1 到 n 中 2 和 5 的质因子个数即可。由于 2 的质因数个数比 5 的多，因此只需要找到 5 的质因数的个数即可得到最终阶乘结果末尾0的个数。更进一步，观察阶乘的过程，5 质因数的产生是**每5个数产生一个5的质因子，每 5 * 5 个数会产生 2 个质因子，每 5 * 5 * 5 个数会产生 3 个质因子…**，因此，该求解过程变成，n 中被 5 整除的个数加上被 5 * 5 整除的个数加上被 5 * 5 * 5 整除的个数…

代码如下

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n = n / 5;
            count += n;
        }

        return count;
    }
}

参考资料

详细通俗的思路分析 - 阶乘后的零 - 力扣（LeetCode）