阶乘末尾0的数量

阶乘末尾0的数量_牛客题霸_牛客网

问题简述

给定一个非负整数 n ，返回 n! 结果的末尾为 0 的数量。

思路1：找规律

• 定义 foo(n) 计算末尾为 0 的数量，然后找规律；

  def foo(n):
      s = 1
      for i in range(1, n + 1):
          s *= i
      s = str(s)
      r = 0
      for i in range(len(s) - 1, -1, -1):
          if s[i] == '0':
              r += 1
          else:
              break
      return r

Python

class Solution:
    def thenumberof0(self , n: int) -> int:
        if n == 0: return 0
    
        import math
        c = int(math.log(n, 5))
        ret = 0
        for i in range(1, c + 1):
            ret += n // (5 ** i)
        return ret

思路2：数学

• 本题实际上求的是 1~n 在因式分解后能提供的 2 和 5 的个数，因为 2 的数量大于 5，因此只要求 5 的个数；

  • 具体来说，能被 5 整除的可以提供 1 个 5，能被 25 整除的可以提供 2 个 5， ...

Python

class Solution:
    def thenumberof0(self , n: int) -> int:
        r = 0
        while n:
            n //= 5
            r += n
        return r