Check if Number is a Sum of Powers of Three

You want to determine if an integer ( n ) can be represented as the sum of distinct powers of three.

We can approach this problem by expressing ( n ) in base 3 and then checking if any digit in the base-3 representation is greater than 1. If there’s a digit greater than 1, then it means that the sum includes two or more of the same power of three, and the answer should be false. If all digits are 0 or 1, it means that the sum only includes distinct powers of three, and the answer should be true.

Here’s the code:

1
2
3
4
5
6
7

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n > 0:
            if n % 3 == 2: # Check if any digit in base-3 representation is 2
                return False
            n //= 3
        return True

Explanation:

1. If the remainder of n divided by 3 is 2, it means that the number cannot be represented as the sum of distinct powers of three, and we return False.
2. Otherwise, we continue to divide n by 3 until n becomes 0.
3. If we reach n = 0 without finding any remainder of 2, it means that n can be represented as the sum of distinct powers of three, and we return True.

Examples:

• For n = 12, the base-3 representation is “110”, so the output is True.
• For n = 91, the base-3 representation is “10101”, so the output is True.
• For n = 21, the base-3 representation is “210”, so the output is False.