原题链接:
https://leetcode.cn/problems/factorial-trailing-zeroes/

想要一个数的结尾多加一个0 最直观的想法就是 * 10
而10 又可以拆解为 2 * 5 也就是说每多一对 2 * 5 就会多一个10 就会多一个0
所以题目转化求 每一个数中的2和5 的数量 有多少对2 5 则结果在就会尾随多少个0
进一步优化->
由于题目求的是0-n的中数的5 那么有5 就一定会有2 也就是说 只要算出5的个数即可

1
2
3
4
5
6
7
8
9
10
class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        for i in range(5,n + 1,5):
            while i % 5 == 0:
                i//=5
                ans = ans + 1

        return ans

进一步优化->
由于0-n中 可能存在前面的数是后面的数的因子 即可能运算出多个重复的5
可以每次直接除5 便可得到当前因子包含5的数量 而这部分5 同样已经在之前被重复运算过了

1
2
3
4
5
6
7
8
9
class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        while n:
            ans+= n//5
            n//=5
        
        return ans