326. Power of Three

📘 題目敘述

給你一個整數 n，如果它是 3 的冪次方（power of three）就回傳 true，否則回傳 false。

如果存在一個整數 x 使得 n == 3^x，那麼 n 就是 3 的冪次方。

條件限制

• -2^31 <= n <= 2^31 - 1

🧠 解題思路（一）用while看餘數

我的想法就是：如果 n 真的是 3^x，那它一定可以被 3 一直整除，直到最後變成 1。

所以我做的事很單純：

• 只要 n 還能被 3 整除，而且 n > 1：
  • 就把 n /= 3（繼續往下剝一層 3）
• 如果某一刻 n == 1：
  • 代表剛好除到 3^0，回傳 true
• 其他情況：
  • 代表中途卡住（不能再整除）或一開始就是不可能（例如 n <= 0），回傳 false

所有變數

• n：目前要檢查的數字（會在迴圈中一路被除以 3）

🪜 主要流程步驟

1. 持續把 n 除以 3（只在「還能整除且還沒到 1」時）

• 條件是：
  • n % 3 == 0
  • 且 n > 1
• 滿足就做：
  • n /= 3

2. 如果 n 變成 1，代表是 3 的冪次方

• n == 1 → true

3. 其他任何情況都不是

• 例如：
  • 中途出現 n % 3 != 0
  • 或者一開始 n <= 0
  • 或者 n 變成 2、-1 之類不可能回到 1 的值
• 直接回傳 false

💻 程式碼實作（一）while版本

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

🧠 解題思路（二）取MAX

這份寫法是用「整數上界」的觀察，做到 O(1) 判斷。

• 在 32-bit signed int 範圍內（最大是 2^31 - 1），最大的 3 的冪次方是：
  • 3^19 = 1162261467
  • 3^20 會超過 2^31 - 1，放不進 int
• 如果 n 是 3^k，那它一定能整除 3^19（因為 3^19 / 3^k = 3^(19-k) 仍是整數）。
• 反過來，如果 n > 0 且 3^19 % n == 0，那 n 的質因數只能是 3（因為 3^19 的質因數只有 3），所以 n 必定是某個 3^k。

因此流程是：

1. 先排除 n <= 0：一定不是 3 的冪次方
2. 設 MAX = 3^19
3. 檢查 MAX % n == 0：成立就回傳 true，否則 false

所有變數

• n：輸入整數
• MAX：在 int 範圍內最大的 3 的冪次方（1162261467，也就是 3^19）

🪜 主要流程步驟

1. 排除不可能的輸入

• 若 n <= 0，直接回傳 false

2. 用最大 3 的冪次方做整除判斷

• 設 MAX = 1162261467
• 回傳 MAX % n == 0

💻 程式碼實作（二）取MAX版本

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n <= 0) return false;
        const int MAX = 1162261467; // 3^19
        return (MAX % n == 0);
    }
};

🔗 題目連結

https://leetcode.com/problems/power-of-three/