当前位置: 面试刷题>> 阶乘后的零(经典算法150题)


题目描述

题目:阶乘后的零

给定一个非负整数 n,计算 n!n 的阶乘)末尾有多少个零。阶乘 n! 是所有小于及等于 n 的正整数的乘积。

阶乘末尾的零是由因子 25 相乘产生的(因为 10 = 2 * 5),而在阶乘的质因数分解中,2 的因子通常比 5 的因子多,所以计算末尾零的个数主要取决于 5 的因子的个数。

示例

  • 输入:n = 5

  • 输出:1 解释:5! = 120,末尾有 1 个零。

  • 输入:n = 10

  • 输出:2 解释:10! = 3628800,末尾有 2 个零。

PHP 代码示例

function trailingZeroes($n) {
    $count = 0;
    while ($n >= 5) {
        $n /= 5;
        $count += (int)$n;
    }
    return $count;
}

// 测试
echo trailingZeroes(5);  // 输出 1
echo "\n";
echo trailingZeroes(10); // 输出 2

Python 代码示例

def trailing_zeroes(n):
    count = 0
    while n >= 5:
        n //= 5
        count += n
    return count

# 测试
print(trailing_zeroes(5))  # 输出 1
print(trailing_zeroes(10)) # 输出 2

JavaScript 代码示例

function trailingZeroes(n) {
    let count = 0;
    while (n >= 5) {
        n = Math.floor(n / 5);
        count += n;
    }
    return count;
}

// 测试
console.log(trailingZeroes(5));  // 输出 1
console.log(trailingZeroes(10)); // 输出 2

逻辑说明

在以上代码中,我们通过不断将 n 除以 5 并累加商(向下取整),直到 n 小于 5 为止。这是因为 n! 中每 5 个连续整数就会贡献一个 5 的因子到质因数分解中(而每 25 个会贡献两个,每 125 个会贡献三个,以此类推),而 2 的因子总是足够的。因此,我们只需要计算 5 的因子的个数即可确定阶乘末尾零的个数。

推荐面试题