【LeetCode】：面试题 16.05. 阶乘尾数

🎁个人主页：我们的五年

🔍系列专栏：C++课程学习

🎉欢迎大家点赞👍评论📝收藏⭐文章

好久没有写文章了，今天碰见了一道有趣的题目，写下来分享一下。

🏆1.问题描述：

 🏆2.问题分析：

🎲优化一：

首先看到这道题的时候，暴力肯定是不行的，n的阶乘可能会是一个很大的数，肯定是会超过int，long long的范围的。

然后再去想其他的方法优化，n的阶乘：1*2*3*……*n。两个数相乘，尾部要新增0，这两个数的最低位的非0必须是（2*5）（4*5）（6*5）（8*5），从这里面可以看出全部都有 5，而且其他的是2的倍数，其实最重要的还是2*5，其他的相乘不会新增0。

一个2和一个5相乘就会在尾部新增一个 0。所以我们计算 1到n之间有个2和5，然后取2和5的最小的个数，就是最后尾部的0的个数。

比如：4*5*5*5=2*2*5*5*5

这里面有2个为2的因子，3个为5的因子，所以一共有2对（2,5）；最后尾部就有2个0。

🎲优化二：

如果根据上面的通过循环计算2和5的个数 ，这样的算法的时间复杂度肯定是要大于logn的，那就会发生时间超限。

然后我们必须在进行优化计算2和5的个数的算法。

我们先来看看不管n是多少，1~n之间，2的因子肯定是要>=5的因子。

所以我们最后只要计算有多少个5，尾部就有多少个0。

🎬1.每五个数中，就有一个是5的倍数。这些都包含一个以上为5的因子。

n/5=n1。

🎬2.但是25有2个5，在25也是5的倍数，计算过一次5，这里也只需要计算一个。

n/25=n2。

🎬125中有3个5,125是5的倍数5的倍数的时候计算过一次，125是25的倍数，在25的时候也计算过一次。最后也只需要计算一次就可以了。

n/125=n3

……

直到计算超过n

最后n1+n2+n3……就是5的个数。

🏆3.实现代码：

一：

class Solution {
public:
    int trailingZeroes(int n) {
        int num=0;
        while(n){
            num+=n/5;
            n/=5;
        }
        return num;
    }
};

二：

class Solution {
public:
    int trailingZeroes(int n) {
        int num=0;

        //最后面i*5的返回可能超过int
        long long i=5;
        for(;i<=n;i*=5)
        {
            num+=n/i;
        }
        return num;
    }
};