Check if Number is a Sum of Powers of Three

LeetCode 1780. Check if Number is a Sum of Powers of Three asks whether a given integer n can be represented as the sum of distinct powers of three. Each power (3^0, 3^1, 3^2, ...) may be used at most once. Return true if such a representation exists, false otherwise.

This problem looks like it might need backtracking or dynamic programming, but there is a much simpler approach hiding in plain sight. It comes down to understanding what "distinct powers of three" really means in terms of number bases.

Why this problem matters

Representing a number as a sum of distinct powers of a base is the same as writing the number in that base and checking that no digit exceeds 1. This connection between "subset selection" and "digit constraints" shows up across many math problems. If you are comfortable converting between bases using repeated division, you can solve an entire family of problems with the same technique.

The key insight

Every positive integer has a unique representation in base 3 (ternary). When you write n in base 3, each digit tells you how many times that power of 3 appears. The digits can be 0, 1, or 2.

If every ternary digit is 0 or 1, then each power of 3 is used at most once, which is exactly what the problem requires. If any digit is 2, it means you would need that power of 3 twice, and the answer is false.

So the algorithm is: repeatedly divide n by 3, and check the remainder at each step. If the remainder is ever 2, return false. If you reduce n all the way to 0 without seeing a 2, return true.

The solution

def checkPowersOfThree(n: int) -> bool:
    while n > 0:
        if n % 3 == 2:
            return False
        n //= 3
    return True

The while loop extracts one ternary digit per iteration, starting from the least significant. n % 3 gives you the current digit, and n //= 3 shifts the number right in base 3. If the digit is 2, you immediately return False. Otherwise, once n hits 0, every digit checked out and you return True.

Visual walkthrough

Let's trace through two examples: n = 12 (should return true) and n = 21 (should return false).

For n = 12, the ternary digits are 0, 1, 1 (reading least to most significant), which is "110" in base 3. No digit equals 2, so 12 = 3 + 9 is a valid decomposition. For n = 21, the ternary representation is "210." That digit of 2 means you would need 3^1 twice, which is not allowed.

Complexity analysis

Time: Each iteration divides n by 3, so the loop runs at most log base 3 of n times. For the constraint n up to 10^7, that is at most 15 iterations.

Space: Only a constant amount of extra memory is used. No arrays, no recursion stack.

The building blocks

1. Base conversion via repeated division

digits = []
while n > 0:
    digits.append(n % base)
    n //= base

This is the standard algorithm for converting an integer to any base. You extract the least significant digit with modulo, then shift the number down with integer division. It appears in problems like Excel Sheet Column Title, Integer to Roman, and anywhere you need to decompose a number by place value.

2. Digit constraint validation

while n > 0:
    if n % 3 == 2:
        return False
    n //= 3
return True

Once you have the digits, the second piece is checking whether they satisfy some constraint. Here the constraint is "no digit equals 2." In Power of Two, the constraint is "exactly one 1-bit." In Happy Number, you compute digit squares. The structure is always the same: extract digits one at a time and validate.

Edge cases

• n = 1: 3^0 = 1. The ternary representation is "1," which has no digit equal to 2. Returns true.
• n = 2: 2 % 3 = 2. You would need two copies of 3^0 = 1. Returns false.
• n = 3: 3 % 3 = 0, then 1 % 3 = 1. Ternary is "10." Returns true (just 3^1).

From understanding to recall

The insight here is simple: checking "sum of distinct powers of three" is the same as checking "all ternary digits are 0 or 1." But simple insights are easy to forget when you are under pressure. Two weeks from now, will you remember to think about base 3 when you see a powers-of-three problem?

Spaced repetition makes sure you do. CodeBricks drills the building blocks, repeated division for base conversion and digit-constraint validation, at increasing intervals. After a few review sessions, the connection between "distinct powers" and "ternary digits" becomes automatic.

Related posts

• Power of Two - similar base-checking problem with binary instead of ternary
• Power of Three - checking if a number is a single power of three
• Happy Number - another math problem involving repeated digit operations

Number theory problems reward you for having a solid mental library of base-conversion techniques. Each one you master makes the next one faster to recognize. CodeBricks helps you build that library one building block at a time.