1780. Check if Number is a Sum of Powers of Three
Description
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 <= 107
Solutions
Solution: Math
- Time complexity: O(1)
- Space complexity: O(1)
JavaScript
js
/**
* @param {number} n
* @return {boolean}
*/
const checkPowersOfThree = function (n) {
if (n === 1) return true;
if (n % 3 === 0) return checkPowersOfThree(n / 3);
if (n % 3 === 1) return checkPowersOfThree((n - 1) / 3);
return false;
};