一步步演算法：計算階乘末尾零的個數

在程式設計面試中，求階乘（n!）結果末尾連續零的個數是經典題目之一。這道題的核心在於理解零的來源：每一個 10 都由 2 與 5 相乘產生，而在階乘的質因數分解中，2 的個數遠多於 5，因此末尾零的個數實際上取決於質因數 5 的總數。

核心觀念

若直接計算 n! 會迅速溢位，且效率低落。正確的做法是統計 1 到 n 中所有 5 的倍數貢獻的 5 的個數：

• 每 5 個數貢獻至少一個 5（如 5、10、15…）
• 每 25 個數額外貢獻一個 5（因為 25 = 5²）
• 每 125 個數再額外貢獻一個 5（125 = 5³）
• 以此類推，直到 5ᵏ > n

高效演算法實作

以下 C 語言函式以 O(log₅ n) 時間複雜度解決問題，無需陣列、無記憶體配置，碾壓原文中模擬乘除的暴力做法：

int countTrailingZeros(int n) {
    if (n < 0) return 0;
    int count = 0;
    for (long long divisor = 5; divisor <= n; divisor *= 5) {
        count += n / divisor;
    }
    return count;
}

程式碼解析

1. 邊界檢查：n < 0 直接回傳 0，階乘未定義。
2. 迴圈累加：divisor 從 5 開始，每輪乘 5（5, 25, 125…），累加 n / divisor 的商。
3. 長整型防溢位：divisor 宣告為 long long，避免乘法過程溢位導致無限迴圈。
4. 時間複雜度：迴圈執行 ⌊log₅ n⌋ 次，極其高效。

範例驗證

延伸思考

若面試官追問「為什麼不數 2 的個數？」，答：2 的個數遠大於 5，5 才是瓶頸。若問「如何擴展到任意進位制？」，則需分解該進位制的質因數，取各質因數個數除以其在進位制中冪次的最小值。

總結

掌握數學本質、拒絕暴力模擬，是演算法優化的關鍵。這個 O(log n) 解法不僅標準、高效，更能展現應聘者的數學直覺與工程思維。