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

一.题目描述
给定一个非负整数N，返回N!结果的末尾为0的数量。
N!是指自然数N的阶乘,即:
二.算法(数学)
因为一个数的阶乘只有是5或5的倍数乘以2的时候才会出现尾随零，并且从阶乘中可以看出来2的个数远大于5的个数，所以由此可以推得求一个数的尾随零数的个数只需看它能除以几个5就有几个零了。

下面是完整代码:

class Solution {
public:
    long long thenumberof0(long long n) {
        long long int ans=0;//可以除的5的个数
        long long int k=5;
        while(n>=k){
            ans+=n/k;
            k=k*5;
        }
        return ans;
    }
};

时间复杂度: 每次都除以一个5所以复杂度是log级别的
空间复杂度: 没有额外空间消耗
优缺点:实现简单，但是思考过程复杂
三.算法(逻辑)
从算法二可以知道本质就是求可以整除5的个数，可以得到
其中[N/5]表示不大于N中对5倍的贡献一个5,[N/5/5]表示不大于N的数中对5*5的倍数贡献一个5......
下面是完整代码：

class Solution {
public:
    long long thenumberof0(long long n) {
        long long int ans=0;
        while(n){
            ans+=n/5;
            n/=5;
        }
        return ans;
    }
};

时间复杂度: 每次都除以一个5所以复杂度是log级别的
空间复杂度: 没有额外空间消耗
优缺点:实现简单，思考起来也比较简单