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.
再帰的な書き方:
実は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サイクルである.
転載先:https://www.cnblogs.com/lowkeysingsing/p/11284242.html
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