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

题意：

• 给定一个非负整数，求该数的阶乘末尾0的数量。

方法一:

• 分析：末尾为0的数量应当取决于质因数5和2的数量，而对于阶乘的数字，显然2的数量在任何情况下都是大于5的数量的，因此直接计算质因数5的数量即可。
• 尝试直接寻找5的数量，遍历含质因数5的数，超时间复杂度。

代码如下:

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 ans=0;
        //寻找5的倍数
        for(int i=5;i<=n;i+=5){
            int tmp=i;
            //计算出含5的因子个数
            while(tmp/5){
                ans++;
                tmp=tmp/5;
            }
        }
        return ans;
    }
};

时间复杂度： , for循环 次,每次for循环内部的while循环是 次,因此加起来是

空间复杂度：。

方法二：

解题思路：

• 从其他方向分析5的数量规律：
  
  如上，我们发现了规律，即5的数量ans=n/5+n/25+n/125+……，此规律也易证其正确性:
  ans=质因子为1个5的数量+质因子为2个5的数量X2+质因子为3个5的数量X3+……+质因子为k个5的数量X5。
  n/5=质因子为1个5的数量+质因子为2个5的数量X1+质因子为3个5的数量X1+……+质因子为k个5的数量X1。
  n/25=质因子为2个5的数量X1+质因子为3个5的数量X1+……+质因子为k个5的数量X1。
  以此类推……
  n/(5^k)=质因子为k个5的数量X1。
  故ans=n/5+n/25+n/125+……+n/(5^k)

• 如下代码，我们将n循环除以5，第一次更新的n即为n/5的值，即阶乘中含至少一个质因数5的个数。下一次除以5，则阶乘中含至少两个质因数5的个数，以此循环，第i次更新即含至少i个质因数5的个数，累加起来为所求结果。

  代码如下：

public:
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    long long thenumberof0(long long n) {
        // write code here
        long long ans=0;
        //将n循环除以5，所得余数即是含5的n次幂的个数。
        while(n/5){
            n=n/5;
            ans+=n;
        }
        return ans;
    }
};

时间复杂度：，仅一个while循环，每次循环除以5。
空间复杂度：。