LeetCode 题解 - 1780. Check if Number is a Sum of Powers of Three

题目链接：1780. Check if Number is a Sum of Powers of Three

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

An integer y is a power of three if there exists an integer x such that $y = 3^x$.

Constraints:

• $1 \leq n \leq 107$

Example 1:

• Input: n = 91
• Output: true
• Explanation: $91 = 3^0 + 3^2 + 3^4$

Example 2:

• Input: n = 21
• Output: false

这道题要求我们判断一个数字是否是不同三次幂之和。“不同”在此处指，不能有一个三次幂出现超过一次。

在讨论不同三次幂之和之前，我们可以先来看一下不同二次幂之和。不同二次幂之和可以表示任意正整数。例如对于数字 23： $$23 = 10111_2 = 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0$$ 对于二次幂之和来说，二次幂之前的系数只有 $0$ 和 $1$ 可以选。所以每个二次幂之和都一定是不同的。

对于三次幂，我们用类似的方式来表示 91 和 21： $$91 = 10101_3 = 1 \times 3^4 + 0 \times 3^3 + 1 \times 3^2 + 0 \times 3^1 + 1 \times 3^0$$

$$21 = 210_3 = 2 \times 3^2 + 1 \times 3^1 + 0 \times 3^0$$

对于三次幂之和来说，三次幂之前的系数可以选 $0$、$1$ 和 $2$。容易发现，要判断一个数字是否是不同三次幂之和，这个数字的三进制表示一定只能存在 $0$ 和 $1$。那么问题就转换为，判断数字的三进制表示中是否存在 $0$ 和 $1$ 以外的数字。

我们先写出把数字转换成三进制表示的代码：

std::vector<unsigned int> toTernary(unsigned int num) {
  std::vector<unsigned int> ternary;
  while (num > 0) {
    ternary.push_back(num % 3);
    num /= 3;
  }

  std::reverse(ternary.begin(), ternary.end());
  return ternary;
}

容易发现，我们只需要检查每次 num % 3 是否大于 $1$ 即可，因此得到题解：

bool checkPowersOfThree(int n) {
  while (n > 0) {
    if (n % 3 > 1) {
      return false;
    }
     n /= 3;
  }
   return true;
}

这个解法也可以推广到检查一个数字是否是不同任意次幂之和。代码为：

bool checkPowersOfM(int n, int m) {
  while (n > 0) {
    if (n % m > 1) {
      return false;
    }
     n /= m;
  }
   return true;
}