題目資訊

• 題目編號: 1780
• 題目連結: Check if Number is a Sum of Powers of Three
• 主題: Math

題目敘述

給定一個整數 n，如果有可能將 n 表示為幾個互不相同的三的冪次之和，則返回 true。否則，返回 false。

當存在一個整數 x 使得 $y = 3^x$ 時，整數 y 是三的冪次。

範例 1:

輸入: n = 12
輸出: true
解釋: 12 = 3^1 + 3^2

範例 2:

輸入: n = 91
輸出: true
解釋: 91 = 3^0 + 3^2 + 3^4

範例 3:

輸入: n = 21
輸出: false

限制條件:

• $1 \leq n \leq 10^7$

直覺

這個問題要求我們判斷給定的整數 $n$ 是否可以表示為不同次方的三的和。三的次方是指形如 $3^x$ 的數字，其中 $x$ 是一個非負整數。關鍵觀察是，每一個三的次方可以被視為三進制數字系統中的一位數字，其中每個係數不是 0 就是 1（因為若要求和中數值互異，則係數不能超過 1）。

這意味著，如果我們能將 $n$ 分解成在三進制中僅使用 0 和 1 作為係數，那麼 $n$ 就可以被表示為不重複的三次方的和。然而，如果任何係數需要為 2，則表示 $n$ 無法被分解為不重複的三次方，並且暗示需要進位，這違反了獨特性的條件。

解法

我們的方法涉及檢查 $n$ 的三進制表示。如果 $n$ 能夠用三進制中的係數 0 和 1 完全表示，那麼它就能夠表示為不重複的三次方之和；否則就不行。

1. 從整數 $n$ 開始。
2. 當 $n$ 大於 0 時，重複以下步驟：
   • 計算 $n$ 除以 3 的餘數，即 $n \mod 3$。
   • 如果餘數是 2，立即返回 false，因為這表示在三進制表示中需要一個 2 的係數，違反了獨特和的條件。
   • 否則，將 $n$ 除以 3 以轉移至下一個更高的三次方。
3. 如果循環在沒有返回 false 的情況下完成，則返回 true。這表明 $n$ 已經被完全減少至允許的三進制系數，顯示它確實可以被表示為不重複的三次方之和。

程式碼

C++

class Solution {
public:
    bool checkPowersOfThree(int n) {
        // 當 n 大於 0 時繼續迴圈
        while (n > 0) {
            // 如果 n 除以 3 的餘數是 2，
            // 則不可能將 n 表示為不同次方的 3 之和
            if (n % 3 == 2) {
                return false;
            }
            // 將 n 除以 3 縮小
            n /= 3;
        }
        // 如果我們完整執行迴圈而沒返回 false，
        // 意味著 n 可以表示為不同次方的 3 之和
        return true;
    }
};

Python

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        # 當 n 大於 0 時，繼續迴圈
        while n > 0:
            # 如果 n 除以 3 的餘數是 2，
            # 那麼就無法將 n 表示為不同三次方的和
            if n % 3 == 2:
                return False
            # 將 n 以 3 為基數縮小
            n //= 3
        # 如果循環完成時沒有返回 False，
        # 這意味著 n 可以表示為不同三次方的和
        return True

複雜度分析

• 時間複雜度: $O(\log_3 n)$ 該演算法的時間複雜度為 $O(\log_3 n)$，因為我們在迴圈的每次迭代中將數字 $n$ 除以 3。該迴圈會持續進行，直到 $n$ 變為 0，在最壞情況下需要 $\log_3 n$ 次迭代。每次迭代僅涉及簡單的算術操作（取模和除法），這些是常數時間操作。

• 空間複雜度: $O(1)$ 空間複雜度是 $O(1)$，因為演算法使用恆定數量的額外空間，無論輸入大小 $n$ 為何。僅使用了少數幾個整數變數，其記憶體分配不依賴於 $n$。