0172._Factorial_Trailing_Zeroes.md

172. Factorial Trailing Zeroes

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/factorial-trailing-zeroes/description/

内容描述

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

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Note: Your solution should be in logarithmic time complexity.

解题方案

思路 1 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

思路就是开始看我们有多少个5，多少个25，多少个125，这些数字成为base，直到这个base比我们的n大了，我们就不继续加了。那这是为什么呢？

因为我们知道想让后面多个0，那一定要是偶数乘以5的形式，我们知道偶数一定是比5多的，所以完全够用，所以直接一直加就行了。

开始我还想复杂了，每次算出最前的base_val，即1有0个0，5有1个0，25有6个0，我是通过算出所在区间然后再叠加，这样显然可以， 但是不如上面的想法来得直接来得快。

beats 99.02%

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

思路 2 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

递归, beats 99.02%

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        return 0 if n < 5 else n // 5 + self.trailingZeroes(n//5)