LeetCode Factorial Trailing Zeroes

发布时间：2020-12-13 21:08:05 所属栏目：PHP教程来源：网络整理

导读：LeetCode解题之Factorial Trailing Zeroes 原题求n的阶乘末尾有几个零。注意点：将时间复杂度控制为log(n) 例子: 输入: n = 5 输出: 1 解题思路通过因数分解知道，10是由2和5相乘得到的，而在n的阶乘中，因子2的数目总是比5多的，所以终究末尾有几个零取

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) 来取得相干源码。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!