题目描述

给你一个整数 n，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true，否则请返回 false。

对于一个整数 y，如果存在整数 x 满足 y == 3^x，我们称这个整数 y 是三的幂。

样例

输入：n = 12
输出：true
解释：12 = 31 + 32

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

输入：n = 21
输出：false

限制

• 1 <= n <= 10^7

算法1

(暴力枚举) $O(2^{\log_3 n})$

1. 最多有 $O(\log_3 n)$ 种 3 的幂次，每一种的系数都有 0 和 1 两种选择。
2. 直接枚举系数的组合，判断是否可以组成目标数字。

时间复杂度

• 共有 $O(\log_3 n)$ 种 3 的幂次，故需要 $O(2^{\log_3 n})$ 的时间来枚举。

空间复杂度

• 仅需要 $O(\log_3 n)$ 的额外空间存储 3 的幂次。

C++ 代码

class Solution {
public:
    bool checkPowersOfThree(int n) {
        vector<int> power(16, 1);
        for (int i = 1; i < 16; i++)
            power[i] = power[i - 1] * 3;

        for (int s = 0; s < (1 << 16); s++) {
            int tot = 0;
            for (int i = 0; i < 16; i++)
                if (s & (1 << i))
                    tot += power[i];
            if (tot == n)
                return true;
        }

        return false;
    }
};

算法2

(数学) $O(\log_3 n)$

1. 将 $n$ 按照三进制展开后，如果某一位上为 2，则不可能写成 3 的幂次之和。这是因为 $3^0 + 3^1 + 3^2 + \cdots + 3^n < 3^{n - 1}$

时间复杂度

• 需要 $O(\log_3 n)$ 的时间来判断。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n) {
            int t = n % 3;
            if (t == 2)
                return false;
            n /= 3;
        }
        return true;
    }
};