Problem Description

You are given an integer n. Your task is to determine whether n can be expressed as the sum of distinct powers of three.

A power of three is any number that can be written as 3^x where x is a non-negative integer. For example, 1 (which is 3^0), 3 (which is 3^1), 9 (which is 3^2), 27 (which is 3^3), and so on.

The key requirement is that the powers of three used in the sum must be distinct - you cannot use the same power of three more than once.

For example:

• 12 can be expressed as 3^2 + 3^1 = 9 + 3 = 12, so it returns true
• 21 can be expressed as 3^2 + 3^1 + 3^0 = 9 + 3 + 1 = 13... wait, that's only 13. Let's try 3^2 + 3^1 + 3^1 = 9 + 3 + 3 = 15... no, we can't use 3^1 twice. Actually, 21 cannot be expressed as a sum of distinct powers of three, so it returns false

The solution leverages the fact that if a number can be expressed as a sum of distinct powers of three, then in its ternary (base-3) representation, each digit must be either 0 or 1. If any digit is 2 or greater, it means we would need to use the same power of three multiple times, which violates the "distinct" requirement.

The algorithm checks each digit of the ternary representation by repeatedly taking n % 3 (which gives the rightmost digit in base-3) and dividing n by 3 (which shifts to the next digit). If any digit is greater than 1, the function returns false. Otherwise, it returns true.

Intuition

To understand why this solution works, let's think about how numbers are represented in different bases. In base-10 (decimal), we use powers of 10: a number like 234 means 2×10^2 + 3×10^1 + 4×10^0. Similarly, in base-3 (ternary), we use powers of 3.

When we convert a number to ternary, each digit tells us how many times we need that particular power of 3. For instance, if n = 12 in decimal, its ternary representation is 110, which means 1×3^2 + 1×3^1 + 0×3^0 = 9 + 3 + 0 = 12.

Now here's the key insight: the problem asks for distinct powers of three. This means each power of 3 can be used at most once. In ternary representation terms, this translates to each digit being at most 1.

Why? Because:

• A digit of 0 means we don't use that power of 3 at all
• A digit of 1 means we use that power of 3 exactly once
• A digit of 2 or more means we'd need to use that power of 3 multiple times

For example, if we had the number 18 (which is 200 in ternary), it would require 2×3^2 = 2×9 = 18. But this means using 3^2 twice, which violates the "distinct" requirement.

Therefore, the problem reduces to a simple check: convert the number to ternary and verify that no digit exceeds 1. The elegant part is we don't need to explicitly convert to ternary - we can check this on-the-fly by repeatedly examining n % 3 (which gives us the current ternary digit) and then doing n //= 3 to move to the next digit. If we ever encounter a remainder greater than 1, we know the number cannot be expressed as a sum of distinct powers of three.

Learn more about Math patterns.

Solution Approach

The implementation follows directly from our mathematical analysis that a number can be expressed as a sum of distinct powers of three if and only if its ternary representation contains only digits 0 and 1.

The algorithm works by examining the ternary digits of n from right to left:

1. Check the current ternary digit: We use n % 3 to get the rightmost digit in the ternary representation. This operation gives us the remainder when dividing by 3, which is exactly the current ternary digit.

2. Validate the digit: If n % 3 > 1, it means the current ternary digit is 2 or greater. This would require using the same power of three multiple times, violating the "distinct" requirement. In this case, we immediately return False.

3. Move to the next digit: We perform integer division n //= 3 to shift to the next ternary digit (moving from right to left in the ternary representation). This is equivalent to removing the rightmost digit we just processed.

4. Repeat until done: We continue this process while n > 0. Each iteration processes one ternary digit.

5. Return the result: If we successfully process all digits without finding any digit greater than 1, we return True.

Here's a step-by-step example with n = 12:

• First iteration: 12 % 3 = 0 (valid), n = 12 // 3 = 4
• Second iteration: 4 % 3 = 1 (valid), n = 4 // 3 = 1
• Third iteration: 1 % 3 = 1 (valid), n = 1 // 3 = 0
• Loop ends, return True

The ternary representation of 12 is 110, confirming that 12 = 1×3^2 + 1×3^1 + 0×3^0 = 9 + 3.

The time complexity is O(log₃ n) since we divide n by 3 in each iteration, and the space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with n = 91:

Step 1: Check if 91 can be expressed as a sum of distinct powers of three.

We'll examine each ternary digit by repeatedly taking n % 3 and n // 3:

• Iteration 1:

  • 91 % 3 = 1 (valid digit, ≤ 1) ✓
  • Update: n = 91 // 3 = 30

• Iteration 2:

  • 30 % 3 = 0 (valid digit, ≤ 1) ✓
  • Update: n = 30 // 3 = 10

• Iteration 3:

  • 10 % 3 = 1 (valid digit, ≤ 1) ✓
  • Update: n = 10 // 3 = 3

• Iteration 4:

  • 3 % 3 = 0 (valid digit, ≤ 1) ✓
  • Update: n = 3 // 3 = 1

• Iteration 5:

  • 1 % 3 = 1 (valid digit, ≤ 1) ✓
  • Update: n = 1 // 3 = 0

Loop ends since n = 0. All digits were 0 or 1, so we return True.

Verification: The ternary representation we found (reading the remainders from bottom to top) is 10101₃. This means:

• 91 = 1×3⁴ + 0×3³ + 1×3² + 0×3¹ + 1×3⁰
• 91 = 81 + 0 + 9 + 0 + 1
• 91 = 81 + 9 + 1 ✓

Now let's see a failing example with n = 21:

• Iteration 1:

  • 21 % 3 = 0 (valid digit, ≤ 1) ✓
  • Update: n = 21 // 3 = 7

• Iteration 2:

  • 7 % 3 = 1 (valid digit, ≤ 1) ✓
  • Update: n = 7 // 3 = 2

• Iteration 3:

  • 2 % 3 = 2 (invalid digit, > 1) ✗
  • Return False immediately

The ternary representation would be 210₃, which would require 2×3² + 1×3¹ + 0×3⁰ = 18 + 3 + 0 = 21. Since we need to use 3² twice (2 × 9), we cannot express 21 as a sum of distinct powers of three.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log₃ n)

The algorithm uses a while loop that continues as long as n > 0. In each iteration:

• We check if n % 3 > 1 (constant time operation)
• We perform integer division n //= 3, which reduces n by a factor of 3

Since we're dividing n by 3 in each iteration, the number of iterations is determined by how many times we can divide n by 3 until it reaches 0. This gives us log₃ n iterations. Each iteration performs constant time operations, so the overall time complexity is O(log₃ n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• No additional data structures are created
• Only the input variable n is modified in-place
• No recursive calls that would use stack space

Therefore, the space complexity is O(1) (constant space).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting Greedy Approach Without Understanding the Mathematical Foundation

A common mistake is trying to solve this problem using a greedy approach by repeatedly subtracting the largest power of 3 that fits into the number. While this might seem intuitive, it can lead to incorrect results.

Incorrect Greedy Approach:

def checkPowersOfThree_wrong(n: int) -> bool:
    used_powers = set()
    power = 1
  
    # Find the largest power of 3 less than or equal to n
    while power * 3 <= n:
        power *= 3
  
    # Greedily subtract powers of 3
    while n > 0 and power >= 1:
        if power <= n:
            if power in used_powers:
                return False
            used_powers.add(power)
            n -= power
        power //= 3
  
    return n == 0

Why it fails: This approach doesn't always find a valid decomposition even when one exists. For example, with n = 12, the greedy approach would first take 9 (3²), leaving 3 (3¹), which works. However, for more complex numbers, the greedy choice might lead to a dead end where the remaining value cannot be expressed with the unused powers.

2. Misunderstanding the Ternary Digit Check

Some might incorrectly implement the check by converting to a string representation first:

Problematic Implementation:

def checkPowersOfThree_problematic(n: int) -> bool:
    # Converting to base-3 string (this doesn't exist in Python by default)
    ternary = ""
    temp = n
    while temp:
        ternary = str(temp % 3) + ternary
        temp //= 3
  
    # Check if all digits are 0 or 1
    for digit in ternary:
        if int(digit) > 1:
            return False
    return True

Issues:

• Unnecessary string operations add overhead
• More complex and error-prone
• Uses O(log n) extra space for the string

Solution: Stick to the mathematical approach of checking digits on-the-fly without storing them.

3. Forgetting Edge Cases

Common missed edge cases:

• n = 0: Should return True (empty sum equals 0)
• n = 1: Should return True (3⁰ = 1)

Fixed Implementation:

def checkPowersOfThree(n: int) -> bool:
    # Handle n = 0 explicitly if needed
    # (though the while loop naturally handles it)
    if n == 0:
        return True
  
    while n:
        if n % 3 > 1:
            return False
        n //= 3
  
    return True

4. Integer Overflow Concerns (Language-Specific)

In languages with fixed integer sizes (like C++ or Java), calculating powers of 3 explicitly might cause overflow:

Potentially Problematic (in other languages):

# This would be problematic in languages with integer overflow
def checkPowersOfThree_overflow_risk(n: int) -> bool:
    powers = []
    power = 1
    while power <= n:  # In C++/Java, power might overflow
        powers.append(power)
        power *= 3
    # ... rest of the logic

Solution: The modulo-based approach avoids this issue entirely since we never calculate large powers of 3 explicitly.

5. Misunderstanding Why Ternary Digits Must Be 0 or 1

Some developers might not fully grasp why a digit of 2 or more in ternary representation means we need duplicate powers:

Clarification:

• In ternary, the digit 2 in position i means 2×3^i
• Since 2×3^i = 3^i + 3^i, we'd need to use 3^i twice
• This violates the "distinct powers" requirement

Correct Understanding Applied:

def checkPowersOfThree(n: int) -> bool:
    while n:
        remainder = n % 3
        # If remainder is 2, it means we need 2×(current power of 3)
        # which requires using the same power twice
        if remainder > 1:
            return False
        n //= 3
    return True