中等

问题描述

给定一个整数 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

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

数学

对于任意一个 $n!$ 而言，其尾随零的个数取决于展开式中 $10$ 的个数，而 $10$ 可由质因数 $2 \times 5$而来，因此 $n!$ 的尾随零个数为展开式中各项分解质因数后 $2$ 的数量 和 $5$ 的数量 中的较小值，而 $5$ 的数量显然比 $2$ 的数量少，因为问题就转化为统计分解质因数后 $5$ 的个数。

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function (n) {
  let ans = 0
  while (n !== 0) {
    n = ~~(n / 5)
    ans += n
  }
  return ans
}

• 时间复杂度：$O(log \, n)$
• 空间复杂度：$O(1)$