Trailing Zeros

题目描述

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

解题方法

我们可以注意到有多少个0只跟有多少2和5有关，而2的数量一定比5多，所以只要关心有多少5就可以。

比如说 5! 有一个5， 11!有两个5 而28!有6个5，5, 10, 15, 20, 25(俩个)

我们可以发现对于5的Power也需要考虑加上它们里面的5，直到不再含有更大的power

所以解题的方法就是

• n / 5, 得到所有5的一次方的数量，加到结果
• 然后n/ (5^2), 得到所有5的二次方的数量，又多了这么多的5，加到结果里
• 5的三次方。。。
• 直到n不大于下一个5的k次方就可以停止了，说明已经不会再有5了

时间复杂度

取决于n大概是5的多少次方，所以是Math.round(Log5(n))

Solution

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 5:
            return 0
        result = 0
        fivePower = 1
        numberOfFive = n / (5 ** fivePower)
        while numberOfFive:
            result += numberOfFive
            fivePower += 1
            numberOfFive = n / (5 ** fivePower)

        return result

Reference

• geeksforgeeks