美文网首页
leetcode--172--阶乘后的零

leetcode--172--阶乘后的零

作者: minningl | 来源:发表于2020-03-28 00:07 被阅读0次

    题目:
    给定一个整数 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;
        }
    };
    

    相关文章

      网友评论

          本文标题:leetcode--172--阶乘后的零

          本文链接:https://www.haomeiwen.com/subject/uvuduhtx.html