172.阶乘后的零

172.阶乘后的零

Category	Difficulty	Likes	Dislikes
algorithms	Medium (45.20%)	589	-

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

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

---

Discussion | Solution

思路

实际上是统计 1-n 有几个 5 的因数。50 为例，除以 5 以后得到 10，说明存在 10 个包含一个因数 5 的数，结果加上 10。10 除以 5，得到 2，说明存在 2 个包含 2 个因数 5 数，之前计算一个因数 5 的时候已经加过这个 2 了，结果再加上 2 即可。最后返回 12 即可。

解答

/*
 * @lc app=leetcode.cn id=172 lang=javascript
 *
 * [172] 阶乘后的零
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function (n) {
  let count = 0;
  while (n > 0) {
    n = Math.floor(n / 5);
    count += n;
  }
  return count;
};
// @lc code=end