Question

172. 阶乘后的零

English Version

题目描述

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

 

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0

 

提示：

• 0 <= n <= 104

 

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

解法

方法一：数学

题目实际上是求 $[1,n]$ 中有多少个 $5$ 的因数。

我们以 $130$ 为例来分析：

1. 第 $1$ 次除以 $5$，得到 $26$，表示存在 $26$ 个包含因数 $5$ 的数；
2. 第 $2$ 次除以 $5$，得到 $5$，表示存在 $5$ 个包含因数 $5^2$ 的数；
3. 第 $3$ 次除以 $5$，得到 $1$，表示存在 $1$ 个包含因数 $5^3$ 的数；
4. 累加得到从 $[1,n]$ 中所有 $5$ 的因数的个数。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

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

class Solution {
  public int trailingZeroes(int n) {
    int ans = 0;
    while (n > 0) {
      n /= 5;
      ans += n;
    }
    return ans;
  }
}

class Solution {
public:
  int trailingZeroes(int n) {
    int ans = 0;
    while (n) {
      n /= 5;
      ans += n;
    }
    return ans;
  }
};

func trailingZeroes(n int) int {
  ans := 0
  for n > 0 {
    n /= 5
    ans += n
  }
  return ans
}

function trailingZeroes(n: number): number {
  let ans = 0;
  while (n > 0) {
    n = Math.floor(n / 5);
    ans += n;
  }
  return ans;
}