LeetCode in Python 172. Factorial Trailing Zeroes階乗後のゼロ

1075 ワード

Given an integer n, return the number of trailing zeroes in n!.
Example 1:
Input: 3Output: 0Explanation: 3! = 6, no trailing zero.Example 2:
Input: 5Output: 1Explanation: 5! = 120, one trailing zero.Note: Your solution should be in logarithmic time complexity.
再帰的な書き方:
class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 5: return 0
        return n/5 + self.trailingZeroes(n/5)

実はnを探しています!式の分解後の5の個数は、5*2=10のため、2は5の前で、個数は必ず5より多い.一方、5の次数、例えば25125625等は複数の5を含み、5を連続的に除算してこれらの余分な5を計算する.n/5+n/25+n/125...すなわち、n/5+n/5/5+n/5/5、以下のwhileサイクルである.
class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        fiveNums = 0
        while n >= 5:
            fiveNums += n / 5
            n = n / 5
          
        return fiveNums

転載先:https://www.cnblogs.com/lowkeysingsing/p/11284242.html