LeetCode--172--阶乘后的0

问题描述：

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

times out:时间复杂度O(nlogn),显然不行

 1 class Solution(object):
 2     def trailingZeroes(self, n):
 3         """
 4         :type n: int
 5         :rtype: int
 6         """
 7         if n == 1 or n == 0:
 8             return 0
 9         nums =[1,1]
10         i = 2
11         while i <= n:
12             nums.append(i*nums[i-1])
13         strs = str(nums[i])
14         return strs.count(0)

改进:

题目是求尾数中0的个数，100return 2，100 == 10* 10十的因子有两个。5！= 5 * 4 * 3 * 2 * 1 = 120 有一个因子10 return 1.有5必有2，求5的个数

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        k = 0
        res = 0
        i = 0
        while n:
            k = n // 5
            res += k
            n = k
        return res

可以去掉变量k

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

2018-09-15 10:47:12