104. 阶乘后的零

题目

给定一个整数 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. 末尾零是怎么来的？

一个末尾零对应一个因子 10，而 10 = 2 × 5。

在 n! 中，因子 2 的数量远远多于因子 5 的数量（因为每隔一个数就有偶数，而 5 的倍数稀疏得多）。

在自然数中，每隔一个数就是偶数（能被2整除），而每隔五个数才是5的倍数。这意味着： 所有偶数都至少贡献一个因子2。 只有5、10、15、20……这样的数才贡献因子5。 所以，在任意一段连续的自然数中，因子2出现的频率天然就比因子5高得多。

因为每个末尾零都需要一个因子2和一个因子5配对形成10。既然因子2总是过剩，那么零的个数就完全取决于因子5的个数。所以我们只需要统计因子5的个数，而不必关心因子2。

所以末尾零的个数 = 因子 5 的总个数。

class Solution {
    fun trailingZeroes(n: Int): Int {
        var num = n
        var count = 0

        // 每一轮都在统计：
        // 当前这一批数里，有多少个数能提供“一个 5”
        // 例如：
        // n = 100 时
        // 第一次统计 100 / 5 = 20
        // 这表示 1..100 里有 20 个数至少能提供一个 5
        while (num > 0) {
            num /= 5
            count += num
        }

        return count
    }
}

复杂度

• 时间复杂度: O(log₅ n)，因为每次除以 5，最多约 log₅ n 次。
• 空间复杂度: O(1)。

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!