題目

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

Note: Your solution should be in logarithmic time complexity.

思路

• 后面的0是2*5產(chǎn)生的， 因?yàn)?的因子數(shù)量永遠(yuǎn)比5多，所以我們只要找有多少個(gè)5就好了
• 像25這種數(shù)，里面有兩個(gè)5的因子，怎么辦？ 舉個(gè)例子，100！里面，有一個(gè)5的因子數(shù)的個(gè)數(shù)是100/5 = 20, 有兩個(gè)5的因子個(gè)數(shù)是100/25 = 4。所以一共有24個(gè)。所以我們就可以用100一直除以5，把所得數(shù)相加。

Python

遞歸

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        #A very smart question, 2 is always ample, so we only need to care about the factor of 5
        return  0 if n == 0 else n/5 + self.trailingZeroes(n/5)
       

循環(huán)

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        #A very smart question, 2 is always ample, so we only need to care about the factor of 5
        res = 0
        while n > 0:
            n /= 5
            res += n
        return res