题目描述：

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

Note: Your solution should be in logarithmic time complexity.

解题思路：

这个题目给的评级是easy，其实只要想到要求n！中0的个数，能够得到0的只有：2,4,5,10,100.。。。而这里面又以5最为稀缺,所以说我们可以得出阶乘的最终结果中的0的数量等于因子中5的数量，比如说10,阶乘含两个0，因为有5,10；30含7个0，因为有5,10,15,20,25（25=5*5）,30。

那么怎么求出有多少个呢？

简单的想法是：令\(f(n)\)表示\(n!\)有多少个0

\[f(n)=f(5)+2 \times f(5^2)+3 \times f(5^3)+\dots
\]

\[f(n)=n/5+f(n/5)
\]

递归版本：

class Solution:

    # @return an integer

    def trailingZeroes(self, n):

        if n < 5:

            return 0

        else:

            return n/5 + self.trailingZeroes(n/5)

迭代版本：

class Solution:

    # @return an integer

    def trailingZeroes(self, n):

        counter = 0

        while  n:

            counter += n / 5

            n /= 5

        return counter

巴特西

【leetcode】Factorial Trailing Zeroes

题目描述：

解题思路：

递归版本：

迭代版本：

最新文章

热门文章