Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
此题寻找 n! 尾部0的个数。
先观察规律:
5! 有 1 个 0; 10! 有 2 个 0;
15! 有 3 个 0; 20! 有 4 个 0;
25! 有 6 个 0; 30! 有 7 个 0......
由此可以观察到,逢 5 的倍数的数,其阶乘多产生 1 个 0。对于 25! ,先用 25 // 5 = 5,会产生 5 个 0;由于商仍然为 5 的倍数, 用 5 // 5 =1,又会产生一个0,因此是6个0。
当 n < 5 时,f(n) = 0; 当 n >= 5 时, f(n) = f(n//5) + n//5
因此,可以用递归的方法,求出末尾 0 的个数。时间复杂度为 O(logn),底数为5。
class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 5:
return 0
return self.trailingZeroes(n//5) + n//5
a = 25
b = Solution()
print(b.trailingZeroes(a)) # 6