172. 阶乘后的零

分析

尾随零的产生是因为 10 = 2 * 5，每次有一个因数 2 和 5 的乘积，都会形成一个 10，从而在阶乘结果的末尾增加一个零

由于阶乘的数值中，因数 2 的出现频率远高于因数 5，所以我们只需要考虑 5 出现的次数，计算 n! 中 5 的因数的个数，即可得到尾随零的个数

1. 计算 n! 中因数 5 的个数
2. 对于 n 中所有能被 5 整除的数，每个数都至少包含一个 5，例如：5, 10, 15, 20...
3. 如果一个数能被 25 整除，则它会包含额外的一个因数 5，比如 25 会有两个因数 5，50 也会有两个因数 5，依此类推
4. 因此，n! 中尾随零的数量就是 n / 5 + n / 25 + n / 125 + ...，直到 5^k > n

时间复杂度

时间复杂度：O(log_5 n) ，因为每次将 n 除以 5，直到 n 小于 5 为止

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution
{
public:
    int trailingZeroes(int n)
    {
      int res = 0;
      while (n)
      {
        res += n / 5;  // 计算能被 5 整除的数
        n /= 5;         // 除以 5，继续计算更高次方的 5
      }
      return res;
    }
};