0172._factorial_trailing_zeros.md

Navigation

• Navigation
• Links:
• Solution 1 转化为另外一个问题
  • 常规写法
  • 递归写法

Links:

1. https://leetcode.com/problems/factorial-trailing-zeroes/
2. https://leetcode-cn.com/problems/factorial-trailing-zeroes/

Solution 1 转化为另外一个问题

5! = 5 * 4 * 3 * 2 * 1 = 120 末尾的零来自于 2 * 5。 果需要产生零，阶乘中的数需要包含 2 和 5 这两个因子。 所以找出阶乘的数中共有多少对 2 和 5 的组合即可。又因为 5 的个数一定比 2 少，问题简化为计算 5 的个数就可以了。

常规写法

class Solution:
    def trailingZeroes(self, n):
        res = 0
        
        while n >= 5:
            res += n // 5
            n //= 5
        
        return res

---

递归写法

class Solution:
    def trailingZeroes(self, n):
        if n < 5:
            return 0
        
        return n // 5 + self.trailingZeroes(n // 5)