题解 | #阶乘末尾0的数量#

题目：阶乘末尾零的数量

描述：给定一个非负整数N，返回N!结果的末尾为0的数量。

N!是指自然数N的阶乘,即:N!=1∗2∗3…(N−2)∗(N−1)∗N。

示例1：输入：3，返回值：0

说明：3!=6

示例2：输入：5，返回值：1

说明：5!=120

示例3：输入：1000000000，返回值：249999998

解法一：思路分析：在思考这个问题的时候，我们很容易想到的一种方法是暴力法破解，就是直接将阶乘的结果计算出来，然后再计算末尾0的数量，但是这种方法导致开销非常大，就比如11！= 39916800，然后再设计程序去判断末尾0的个数，虽然很简单，但是其阶乘计算相当复杂，会占用大量的内存空间，开销问题值得深思，而且如果计算一个很大的数值类型的时候，会发生溢出问题，所以其中的耗时就可想而知了，所以我们不采用暴力法进行运算。

通过仔细分析问题，会发现如果末尾出现0的话，主要是10或者10的倍数相乘导致的结果，10是5与2或4或6或8相乘而得到的。也就是说，最终末尾出现0的是5、10等自身与偶数相乘后产生的，所以我们在具体分析时以5的倍数为例，首先考虑偶数，只要有足够的偶数与5的倍数相乘就会产生0的出现，可以以5为起始点开始考虑，设置一个循环体进行判断幂次项，最终将结果加进count里，最后输出结果值。

实例分析：输入：10，返回值：2
图片说明

C++核心代码：

class Solution {
public:
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    long long thenumberof0(long long n) {
        // write code here
        long count = 0;//计数的次数
        long def;
        for (long i = 5; i <= n; i+=5) {//for循环内部的i都是5的倍数，因此首先进行+1操作
            count++;
            def = 25;
            //判断是不是25的倍数，根据每次def的变化进行+1操作
            while (i % def == 0) {
                count++;
                def *= 5;
            }
        }
        return count;
    }
};

因为该算法的时间运行比较长，并不符合要求的时间，其效率比较差，所以应该采用解法2，经过分析发现代码的时间复杂度是 $O(N/5)$ ~ $O(N)$ ，在该算法中不需要额外的内存空间，所以空间复杂度为 $O(1)$ 。

解法二：

思路分析：其次，我们再次进行划分操作，发现实际上末尾为0的数量应该取决于质因数5和2的数量，因为 $4 * 5 = 2 * 2 * 5$ ， $8 * 5 = 2 * 2 * 2 * 5$ ，所以对于阶乘的数值，可以直接计算质因数5的数量即可，因为2的倍数在任何情况下都是大于5的，我们可以简要的分析：
图片说明
——5的数量实际上为 $res = n/5 + n/25……$ ，所以在代码设计中也可以采用将n循环除以5，循环判断累加结果值即可。

实例分析：输入为25

示例图
C++核心代码为：

class Solution {
public:
    /**
     * the number of 0
     * @param n long长整型the number
     * @return long长整型
     */
    long long thenumberof0(long long n) {
        // write code here
        long long res = 0;
        while(n / 5){//将n循环除以5判断
            n = n / 5;
            res += n;
        }
        return res;
    }
};

其采用的是特殊值判断法，不断的寻找5的个数来判断最终结果值，所以其时间复杂度为 $O(logN)$ （向下取整），其不占用内存空间，所以空间复杂度为 $O(1)$ 。