您当前位置：首页 > php开源 > php教程 > LeetCode Factorial Trailing Zeroes

LeetCode Factorial Trailing Zeroes

来源：程序员人生发布时间：2016-06-16 14:05:59 阅读次数：2113次

LeetCode解题之Factorial Trailing Zeroes

原题

求n的阶乘末尾有几个零。

注意点：

将时间复杂度控制为log(n)

例子:

输入: n = 5

输出: 1

解题思路

通过因数分解知道，10是由2和5相乘得到的，而在n的阶乘中，因子2的数目总是比5多的，所以终究末尾有几个零取决于其中有几个5。1到n中能够整除5的数中有1个5，能整除25的数有2个5（且其中1个在整除5中已计算过）…所以只要将n不断除以5后的结果相加，就能够得到因子中所有5的数目，也就得到了终究末尾零的数目。

AC源码

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


if __name__ == "__main__":
    assert Solution().trailingZeroes(25) == 6

欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来取得相干源码。

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 Java String源码解析

下一篇 尼玛，Timer也会休眠啊。

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点