Code Implementation

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        # Repeatedly check the remainder when dividing by 3
        while n > 0:
            if n % 3 == 2:
                return False
            n //= 3
        return True
      

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n > 0) {
            if (n % 3 == 2) return false;
            n /= 3;
        }
        return true;
    }
};
      

class Solution {
    public boolean checkPowersOfThree(int n) {
        while (n > 0) {
            if (n % 3 == 2) return false;
            n /= 3;
        }
        return true;
    }
}
      

var checkPowersOfThree = function(n) {
    while (n > 0) {
        if (n % 3 === 2) return false;
        n = Math.floor(n / 3);
    }
    return true;
};
      

Problem Description

Given an integer n, determine if it can be expressed as the sum of distinct powers of three. In other words, can you write n as 3^0 + 3^1 + ... + 3^k for some set of non-repeating exponents?

• Each power of three can be used at most once.
• Return true if such a representation is possible, and false otherwise.

• 1 ≤ n ≤ 10⁷
• Each power of three is used at most once (no repeats).

Thought Process

At first glance, this task seems similar to the "subset sum" problem: can we pick a subset of powers of three that adds up to n? A brute-force approach might try all combinations of powers of three up to n, but this quickly becomes inefficient as n grows.

However, there's a key insight: every number can be represented in base 3, just like binary (base 2) for powers of two. If n can be written as a sum of distinct powers of three, then its base-3 representation should only contain digits 0 or 1 (not 2). If a digit "2" appears, it would mean we need to use the same power of three twice, which isn't allowed.

This observation allows us to check the base-3 digits of n efficiently, rather than checking all possible subsets.

Solution Approach

To determine if n is a sum of distinct powers of three, we use the following algorithm:

1. Divide n by 3 repeatedly: At each step, check the remainder (n % 3).
2. If the remainder is 2: This means the base-3 representation at that digit is 2, so n can't be made from distinct powers of three. Return false.
3. If the remainder is 0 or 1: Continue dividing n by 3 and repeat the process.
4. If n reaches 0: All digits were 0 or 1, so n can be written as the sum of distinct powers of three. Return true.

This method is efficient because it only requires checking the digits of n in base 3, which takes O(log₃(n)) steps.

Example Walkthrough

Example: Let n = 91

• First, check 91 % 3 = 1 (OK)
• Now, 91 // 3 = 30
• Check 30 % 3 = 0 (OK)
• Now, 30 // 3 = 10
• Check 10 % 3 = 1 (OK)
• Now, 10 // 3 = 3
• Check 3 % 3 = 0 (OK)
• Now, 3 // 3 = 1
• Check 1 % 3 = 1 (OK)
• Now, 1 // 3 = 0 (done)

• 21 % 3 = 0
• 21 // 3 = 7
• 7 % 3 = 1
• 7 // 3 = 2
• 2 % 3 = 2 (Not allowed!)

Time and Space Complexity

Brute-force Approach:

• Would require generating all subsets of powers of three up to n, which is exponential in the number of powers (O(2^k)).
• This is not feasible for large n.

• Each division by 3 reduces n by a factor of 3, so we perform O(log₃(n)) steps.
• Each step is O(1), so total time is O(log n).
• Space complexity is O(1) since we only use a few variables.

Summary

The key insight to this problem is recognizing the connection to base-3 representation. If a number's base-3 digits are all 0 or 1, it can be written as a sum of distinct powers of three. This allows us to check the condition efficiently, without needing to try all possible combinations. The approach is elegant, fast, and leverages number representation theory for an optimal solution.