Problem
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 <= 10^7
Solution (Java)
class Solution {
public boolean checkPowersOfThree(int n) {
while (n != 0) {
int rem = n % 3;
n /= 3;
if (rem == 2 || n == 2) {
return false;
}
}
return true;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).