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.
Solution:
NOTE: brute force是先计算n!，再不停的//10，直到%10 != 0。但是肯定不是最优解，然后0是一对2和5的组合，于是统计2和5作为因子出现的总次数，然后取min就行了。然后思考了一下2和5如何在log n时间内求出来，比如2，会不会是分治，比如n分成 0- 和
到n，然后只需要求其中之一，但是发现不行。然后发现2肯定比5多，所以只需要统计5的个数。然后思考如何更高效找到5的个数，比如用字典存储10中5只有1个，然后10×5就有2个5，后面求20×5可以递归。最后发现其实只需要一层层求解就行了，而不是分析一个个数字。
class Solution:
def trailingZeroes(self, n: int) -> int:
ret = 0
while n//5 != 0:
ret += n//5
n //= 5
return ret
Runtime: 36 ms, faster than 82.02% of Python3 online submissions for Factorial Trailing Zeroes.
Memory Usage: 13.8 MB, less than 5.43% of Python3 online submissions for Factorial Trailing Zeroes.
sample 28 ms submission
class Solution:
def trailingZeroes(self, n: int) -> int:
if n == 0:
return 0
return n // 5 + self.trailingZeroes(n // 5)
