LeetCode 筆記：階乘尾數零的個數

題目描述

給定一個整數 n，回傳 n!（n 的階乘）結果末尾連續 0 的個數。要求演算法時間複雜度為對數級 O(log n)。

題目分析

暴力法先算出 n! 再數尾數 0，但 n 稍大就會溢位，不可行。關鍵在於質因數分解：n! = 2^x * 3^y * 5^z * ...。每個 10 由一個 2 和一個 5 相乘產生，尾數 0 的個數等於 min(x, z)。證明可知階乘中 2 的指數一定大於 5 的指數，所以 min(x, z) = z。問題轉化為求 n! 中質因數 5 的總指數。

計算公式：z = n/5 + n/25 + n/125 + ...（整數除法），直到商為 0。這正是對數時間複雜度的來源。

示例代碼 (C++)

#include <iostream>
using namespace std;

class Solution {
public:
    int trailingZeroes(int n) {
        int result = 0;
        while (n) {
            result += n / 5;
            n /= 5;
        }
        return result;
    }
};

小結

代碼極短，但從題目要求推導到簡單運算需要數學直覺。理解質因數分解中 2 與 5 的關係是關鍵，體現了演算法設計中「化繁為簡」的思想。