中等

问题描述

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：n = 21
输出：false

提示：

• 1 <= n <= 107

回溯

枚举各个可能的组合，若能得到目标值即为 $true$

/**
 * @param {number} n
 * @return {boolean}
 */
var checkPowersOfThree = function (n) {
  const list = [1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907]
  const dfs = (idx, sum) => {
    if (sum === n) return true
    for (let i = idx; i < list.length; ++i) {
      if (dfs(i + 1, sum + list[i])) {
        return true
      }
    }
    return false
  }
  return dfs(0, 0)
}

• 时间复杂度：$O(n \times \log{n})$
• 空间复杂度：$O(1)$

数学

可以将 $n$ 转换成 $3$ 进制。如果 $n$ 的 $3$ 进制表示中每一位均不为 $2$，那么答案为 $true$。

/**
 * @param {number} n
 * @return {boolean}
 */
var checkPowersOfThree = function (n) {
  while (n > 1) {
    if (n % 3 === 2) return false
    n = ~~(n / 3)
  }
  return true
}

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(1)$