LeetCode 326 Power of Three：判斷整數是否為 3 的冪

題目大意

給定整數 n，判斷是否存在整數 k ≥ 0 使得 3^k = n。進階要求：不使用迴圈/遞歸。

解法一：迴圈除法（基礎版）

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n < 1) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
    }
};

• 時間：O(log₃ n)，空間：O(1)。
• 負數、零直接回傳 false。

解法二：數學極值法（無迴圈/遞歸）

32 位有號整數最大值 2^31 - 1 = 2147483647。最大的 3 的冪為 3^19 = 1162261467。
若 n > 0 且 1162261467 % n == 0，則 n 為 3 的冪（因 3 為質數，其冪的約數只能是 3 的冪）。

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

• 時間：O(1)，空間：O(1)。滿足進階要求。

解法三：對數法（浮點精度風險）

bool isPowerOfThree(int n) {
    if (n <= 0) return false;
    double log3 = log10(n) / log10(3);
    return abs(log3 - round(log3)) < 1e-10;
}

需處理浮點誤差，不如極值法穩健。

解法四：整數集合查表（通用擴展）

預計算所有 32 位範圍內的 3 的冪存入 unordered_set，查詢 O(1)。適用於多次查詢場景。

複雜度總結