【前端算法】阶乘后的零,两次遍历

415 阅读1分钟

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

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

** 解题代码:**

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
 let result = 1;
 let i = 1;
 while (i <= 5) {
  result *= i;
  i++;
 };
 var num = 0;
 while (n > 0) {
  n = (n - (n % 5)) / 5;
  num += n;
 }
 return num
};

知识点

  • 求阶乘数字后面的零

末尾0的个数取决于乘法中因子2和5的个数。显然乘法中因子2的个数大于5的个数,所以我们只需统计因子5的个数。

5!
求55/5 = 1//120 后面一个零
5的倍数的数有: 1024 / 5 = 204个
是25的倍数的数有:1024 / 25 = 40个
是125的倍数的数有:1024 / 125 = 8个
是625的倍数的数有:1024 / 625 = 1个
所以1024! 中总共有204+40+8+1=253个因子5。
也就是说1024! 末尾有2530

本文使用 mdnice 排版