leetcode--172--阶乘后的零

题目:
给定一个整数 n,返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

链接:https://leetcode-cn.com/problems/factorial-trailing-zeroes

思路:
1、题目要求统计阶乘后0的个数,而0只和2和5有关。由于阶乘中2的倍数明显大于5,所以这道题主要是计算n的阶乘中5的个数
2、n的阶乘中5的个数 = n/5 + n/(5* 5) + n/(5* 5* 5) ...

Python代码:

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        ret = 0
        while n>=5:
            ret += n/5
            n /= 5
        return ret

C++代码:

class Solution {
public:
    int trailingZeroes(int n) {
        int ret=0;
        while(n>=5){
            ret += n/5;
            n /= 5;
        }
        return ret;
    }
};
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容