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 == 3x.
Example 1:
Input: n = 12 Output: true Explanation: 12 = 31 + 32
Example 2:
Input: n = 91 Output: true Explanation: 91 = 30 + 32 + 34
Example 3:
Input: n = 21 Output: false
Constraints:
1 <= n <= 107class Solution {
public boolean checkPowersOfThree(int n) {
int[] exp = new int[16];
exp[0] = 1;
int i = 1;
for (; i < 16 && exp[i - 1] < n; i++)
exp[i] = exp[i - 1] * 3;
for (int rt = --i, sum = n; rt >= 0 && sum > 0; rt--) {
if (exp[rt] <= sum)
sum -= exp[rt];
if (sum == 0)
return true;
}
return false;
}
}class Solution {
public boolean checkPowersOfThree(int n) {
while (n > 0) {
if (n % 3 == 2) // extract current LSB
return false;
n /= 3; // right shift ternary bit
}
return true;
}
}