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

阶乘末尾0的数量

http://www.nowcoder.com/practice/aa03dff18376454c9d2e359163bf44b8

题意:

  • 给定一个非负整数,求该数的阶乘末尾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。
空间复杂度:

全部评论

相关推荐

10-24 11:10
山西大学 Java
若梦难了:哥们,面试挂是很正常的。我大中厂终面挂,加起来快10次了,继续努力吧。
点赞 评论 收藏
分享
勇敢的联想人前程似锦:如果我是你,身体素质好我会去参军,然后走士兵计划考研211只需要200多分。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务