阶乘中的零

发表于 | 分类于 |
字数统计: 535 字 | 阅读时长 ≈ 2 分钟

题目描述：给定一个整数 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. 一个末尾0的出现需要依靠2*5
  2. 每两个数比如1,2,3,4…就会出现存有2因子的数
  3. 每5个数才会出现存有5因子的数，比如1,2,3,4,5,6,7,8,9,10…
  4. 也就是说找到5因子的个数总能找到2因子和它配对，问题变成了1…n中具有几个5因子
  5. 需要注意某些数，比如25,125,625是存在多个5因子的,比如25有两个5因子,125有三个5因子
  6. 其中25是每25个出现一次，125是125个出现一次….
  7. 综上所述，每5个会有一个base的5因子，能够有a个25的就加a,能够有b个125的就加b….

以126为例：

  • 第一次除以5时得到25，表明存在25个包含1个5的数。
  • 再次除以5得到5，表明存在5个包含两个5乘积的数，由于第一个5在第一轮已被计算，因此第二轮只需简单的相加。
  • 同理，第三次除以5得到一，存在一个包含三个5乘积的数。
  • 最后累加，得到126！结果尾数包含31个零的结论
1
2
3
4
5
6
7
8
var trailingZeroes = function(n) {
  let count = 0
  while(n) {
    n = Math.floor(n / 5) 
    count += n
  }
  return count
};

复杂度分析

  • 时间复杂度：O(logn)。在这种方法中，我们将 n 除以 5 的每个幂。根据定义，5 的 log5n 幂小于或等于 n。由于乘法和除法在 32 位整数范围内，我们将这些计算视为 O(1)。因此，我们正在执行 log5n⋅O（1）=logn 操作
  • 空间复杂度：O(1)，只是用了常数空间。