面试题 16.05. 阶乘尾数

面试题 16.05. 阶乘尾数

设计一个算法，算出 n 阶乘有多少个尾随零。
示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例  2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

思路

求 0 尾数，即看能有多少个因子能 2 和 5 组成 10，除 0 外所有的偶数都含有因子 2，所以 2 的数量是比 5 多得多的，所以只需要计算 5 的数量。
第一步直接除以 5，得到 5 的数量加入结果中。
假设数无限大，我们可以知道，25 = 5 _ 5，所以每隔 25 个缺少了一个 5。
125 = 5 _ 5 * 5，所以每隔 125 个又缺少了一个 5。
以此类推，所有缺少的 5 都要加上。
所以 count = n / 5 + n / 25 + n / 125 …
优化一下 count = n / 5 + n / 5 / 5 + n / 5 / 5 / 5 …
当 n<5 时，得到为 0，终止循环。

解答

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function (n) {
  let count = 0;
  while (n >= 5) {
    n = parseInt(n / 5);
    count += n;
  }
  return count;
};