Check if Number is a Sum of Powers of Three

Return true if n can be written as a sum of distinct powers of 3, and false otherwise. You may use 3^0 = 1, 3^1 = 3, 3^2 = 9, and so on, but each power may appear at most once.

Example 1:

Input: n = 4

Output: true

Explanation: Use 1 + 3 = 4. These are the distinct powers 3^0 and 3^1.

Example 2:

Input: n = 2

Output: false

Explanation: The only power of three no greater than 2 is 1. Reaching 2 would require using it twice, which is not allowed.

Example 3:

Input: n = 10

Output: true

Explanation: Use 1 + 9 = 10. These are the distinct powers 3^0 and 3^2.

Constraints:

• 1 <= n <= 10000000