LeetCode 172. 阶乘后的零

题目描述

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

示例 1:

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

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

题解

思路

1. 所有末尾的 0 来源于 10 的个数。
2. 10 来源于 2 × 5 。
3. 所以需要统计所有 5 与 2 乘积的个数。例如：4 × 5 = 20 ……
4. 因为偶数个数比较多， 2 的个数远远足够，所以只统计因数 5 的个数即可。

• 例一：

  23! 的因数中有 5, 10, 15, 20 ，分解为 5, (2×5), (3×5), (4×5) ，一共有 4 个 5 。

  所以 23! 末尾有 4 个 0。

• 例二：

  100! 其中有 100 ÷ 5 = 20 个 5，所以有 25 个 0。

  但是其中 25 = 5 × 5，会产生一个额外的 0。所以 100 ÷ 25 = 4，会产生额外的 4 个 0。

  所以最后 100! 有 25 + 4 = 29 个 0。

1. 所以还需要考虑 5, 5×5, 5×5×5, 5ⁿ 。

• 例三：

  4617!

  5¹ ：4617 ÷ 5 = 923，所以有 923 个 0。

  5² ：4617 ÷ 25 = 184，所以有 184 个 0。

  5³ ：4617 ÷ 125 = 36，所以有 36 个 0。

  5⁴ ：4617 ÷ 625 = 7，所以有 7 个 0。

  5⁵ ：4617 ÷ 3125 = 1，所以有 1 个 0。

  5⁶ ：4617 ÷ 15625 = 0，已经小于 1 ，不再继续。

  所以 4617! 有 923 + 184 + 36 + 7 + 1 = 1151 个 0。

代码

// C++
int trailingZeroes(int n) {
    int count = 0;
    for (long long i = 5; n / i > 0; i *= 5) {
        count += (n / i);
    }
    return count;
}

参考链接

• Simple C/C++ Solution (with detailed explaination)), LeetCode discuss.