LeetCode 326. 3 的冪：無循環遞歸 O(1) 數學解法詳解

LeetCode 326. 3 的冪：無循環遞歸 O(1) 數學解法詳解

判斷一個整數是否為 3 的冪次方。進階要求：不使用循環/遞歸。本文揭示利用 32 位有符號整數範圍內最大 3 的冪數（3^19 = 1162261467）的數學特性，實現 O(1) 時間常數空間判斷。

核心數學洞察

在 32 位有符號整數範圍內（-2^31 ~ 2^31-1），最大的 3 的冪次方是：

3^0 = 1
3^1 = 3
...
3^19 = 1162261467
3^20 = 3486784401 > INT_MAX (2147483647)

因此，範圍內所有 3 的冪次方都是 1162261467 的約數。即：n > 0 且 1162261467 % n == 0 則 n 是 3 的冪。

C 語言實現

bool isPowerOfThree(int n) {
    // 1162261467 = 3^19，int範圍內最大的3的冪
    return (n > 0 && 1162261467 % n == 0);
}

為什麼這行得通？

• 3 是質數，其冪次方的約數只能是 3 的更低冪次方（或 1）。
• 若 n = 3^k (k ≤ 19)，則 3^19 % 3^k = 0。
• 若 n 不是 3 的冪，則必包含 3 以外的質因子，無法整除 3^19。

邊界情況

• n ≤ 0：直接返回 false（負數、0 不是冪數）。
• n = 1：3^0 = 1，1162261467 % 1 == 0，正確返回 true。

擴展：其他進制冪的判斷

同理可得：

• 2 的冪：`n > 0 && (n & (n-1)) == 0`（位運算最快）或 `1073741824 % n == 0` (2^30)。
• 4 的冪：`n > 0 && (n & (n-1)) == 0 && (n % 3 == 1)`。

總結

利用數據類型範圍內最大冪數的約數特性，將「是否為冪」轉化為「是否為最大冪數的約數」，巧妙避開循環遞歸，達到 O(1) 時間、O(1) 空間的極致優雅解法。這是數學思維在算法優化中經典應用。