LeetCode 172. Factorial Trailing Zeroes：對數時間計算階乘尾部零

問題描述

給定 n，求 n! 末尾連續 0 的個數。要求對數時間複雜度。

數學原理

尾部 0 由因子 10 = 2 × 5 產生。階乘中因子 2 的個數遠多於 5，故 0 的個數等於因子 5 的個數。
25 = 5² 貢獻兩個 5，125 = 5³ 貢獻三個，以此類推。

遞歸/迭代公式

zeros(n) = n/5 + n/25 + n/125 + ... = n/5 + zeros(n/5)

// 遞歸
long trailingZeros(long n) {
    return n/5 == 0 ? 0 : n/5 + trailingZeros(n/5);
}

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

複雜度分析

• 時間：O(log₅ n)，滿足對數要求
• 空間：遞歸 O(log n) 棧，迭代 O(1)

暴力法（不可取）

直接計算階乘再數 0：n≥13 即溢出 32 位整數，n≥21 溢出 64 位。時間 O(n) 且實際不可行。