leetcode_172

发表于   |   分类于

Factorial Trailing Zeroes

题目戳这

题意

给定一个数字n，求n!的后缀零

解法

我们可以发现，后缀零是由2和5的乘积产生的，我们可以将n!进行分解，用num2来表示分解后2的个数，num5来表示分解后5的个数，那么最后的结果就是min(num2, num5).通过分解比较小的几个阶乘，比如 5!=5*4*3*2*1 = 2^3*5^1*3，含有2阶乘的个数要大于5的，则当数字越来越大的时候，2的个数更加要超过5，所以我们只要看5的个数即可。那么n!中含有因子5的个数是多少呢？

经过检验可以得知，应该为floor(n/5)，但是有几个例外的情况，就是比如25(55),125(55*5)…..这些个含有5的个数是大于floor(n/5)的，所以当n/5后，我们还要检验n/25,n/125含有5的情况，故用一个while循环不断floor(n/5)直到n为0

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        while n:
            ans += n//5
            n //= 5
        
        return ans