LeetCode 1780 - Check if Number is a Sum of Powers of Three
The problem asks whether a given integer n can be expressed as the sum of distinct powers of three. A power of three is any number of the form: where x is a non-negative integer. That means the valid powers are: - 3^0 = 1 - 3^1 = 3 - 3^2 = 9 - 3^3 = 27 - and so on.
Difficulty: 🟡 Medium
Topics: Math
Solution
Problem Understanding
The problem asks whether a given integer n can be expressed as the sum of distinct powers of three.
A power of three is any number of the form:
$3^x$
where x is a non-negative integer. That means the valid powers are:
3^0 = 13^1 = 33^2 = 93^3 = 27- and so on.
The word "distinct" is extremely important. Each power of three can be used at most once. For example:
12 = 9 + 3, valid because both powers are distinct21 = 9 + 9 + 3, invalid because9is used twice
The input consists of a single integer n, and we must return:
trueif such a representation existsfalseotherwise
The constraints are relatively small:
1 <= n <= 10^7
This tells us that brute force solutions may still be possible, because the number of powers of three below 10^7 is small. However, the problem is really about identifying a mathematical property that leads to a cleaner and more optimal solution.
An important observation is that powers of three grow quickly:
3^0 = 1
3^1 = 3
3^2 = 9
3^3 = 27
...
3^15 = 14348907
Since 3^15 already exceeds 10^7, there are only about 15 relevant powers to consider.
Some important edge cases include:
n = 1, which is simply3^0- Numbers like
2, which cannot be represented because the only available powers are1, 3, 9, ... - Numbers that require repeating a power, which is not allowed
- Large values close to
10^7
The key challenge is determining whether every power is used at most once.
Approaches
Brute Force Approach
A straightforward solution is to first generate every power of three less than or equal to n, then try every possible subset of those powers.
For example, if the powers are:
[1, 3, 9, 27]
we can test every subset:
[]
[1]
[3]
[1,3]
[9]
[1,9]
...
and check whether any subset sums to n.
This works because the problem explicitly asks whether some combination of distinct powers equals n.
The issue is that subset generation is exponential. If there are k powers of three, then there are:
$2^k$
possible subsets.
Even though k is small here, exponential algorithms are generally undesirable and unnecessary when a direct mathematical observation exists.
Optimal Approach
The key insight comes from base-3 representation.
Any number written in base 3 uses digits:
0, 1, 2
For example:
12 in base 3 = 110
which means:
$12 = 1\cdot3^2 + 1\cdot3^1 + 0\cdot3^0$
Notice something important:
- A digit
0means that power is not used - A digit
1means that power is used once - A digit
2means that power would need to be used twice
Since the problem requires distinct powers, every base-3 digit must be either 0 or 1.
Therefore:
- If any digit in the ternary representation is
2, the answer isfalse - Otherwise, the answer is
true
This gives a very elegant greedy and mathematical solution.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^k) | O(k) | Generates all subsets of powers of three |
| Optimal | O(log₃ n) | O(1) | Checks ternary digits directly |
Algorithm Walkthrough
- Start with the given integer
n. - Repeatedly examine the remainder when dividing
nby3.
The operation:
$n \bmod 3$
gives the current ternary digit.
3. If the remainder is 2, immediately return false.
A ternary digit of 2 means we would need to use the same power of three twice, which violates the requirement that all powers be distinct.
4. Otherwise, divide n by 3 using integer division.
This shifts the ternary representation one digit to the right and allows us to process the next power of three.
5. Continue until n becomes 0.
6. If the loop finishes without encountering a digit 2, return true.
Why it works
Every integer has a unique base-3 representation. Each ternary digit corresponds to how many times a particular power of three is used.
If all digits are only 0 or 1, then the number is exactly a sum of distinct powers of three. If any digit is 2, then at least one power must be used more than once, which is forbidden.
Because base representations are unique, this condition is both necessary and sufficient.
Python Solution
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
while n > 0:
if n % 3 == 2:
return False
n //= 3
return True
The implementation directly follows the mathematical observation about ternary digits.
The while loop processes the number digit by digit in base 3. At each iteration:
n % 3
extracts the current ternary digit.
If that digit equals 2, the function immediately returns False because the representation would require reusing a power of three.
Otherwise, the algorithm removes the processed digit using:
n //= 3
Eventually, all digits are processed and n becomes 0. If no invalid digit was found, the function returns True.
The solution is concise because the mathematics eliminates the need for recursion, backtracking, or subset generation.
Go Solution
func checkPowersOfThree(n int) bool {
for n > 0 {
if n%3 == 2 {
return false
}
n /= 3
}
return true
}
The Go implementation is almost identical to the Python version.
Go uses integer division automatically when both operands are integers, so:
n /= 3
correctly removes the current ternary digit.
There are no overflow concerns because the maximum input value is only 10^7, well within Go's int range.
No additional memory allocations or slices are required, so the implementation remains constant space.
Worked Examples
Example 1
Input: n = 12
Base-3 representation of 12 is:
110
Trace through the algorithm:
| Iteration | n | n % 3 | Action |
|---|---|---|---|
| 1 | 12 | 0 | Valid digit |
| 2 | 4 | 1 | Valid digit |
| 3 | 1 | 1 | Valid digit |
| End | 0 | - | Return true |
Representation:
$12 = 3^2 + 3^1$
So the answer is true.
Example 2
Input: n = 91
Trace:
| Iteration | n | n % 3 | Action |
|---|---|---|---|
| 1 | 91 | 1 | Valid digit |
| 2 | 30 | 0 | Valid digit |
| 3 | 10 | 1 | Valid digit |
| 4 | 3 | 0 | Valid digit |
| 5 | 1 | 1 | Valid digit |
| End | 0 | - | Return true |
Representation:
$91 = 3^4 + 3^2 + 3^0$
So the answer is true.
Example 3
Input: n = 21
Trace:
| Iteration | n | n % 3 | Action |
|---|---|---|---|
| 1 | 21 | 0 | Valid digit |
| 2 | 7 | 1 | Valid digit |
| 3 | 2 | 2 | Invalid digit, return false |
The ternary representation contains a digit 2, meaning one power of three would need to be used twice.
Therefore the answer is false.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(log₃ n) | One iteration per ternary digit |
| Space | O(1) | Only a few variables are used |
The algorithm repeatedly divides n by 3, so the number of iterations equals the number of digits in the base-3 representation of n.
Since logarithms differ only by a constant factor, this is effectively logarithmic time complexity.
The space complexity is constant because no additional data structures grow with input size.
Test Cases
solution = Solution()
assert solution.checkPowersOfThree(1) == True # smallest valid input
assert solution.checkPowersOfThree(2) == False # requires repeated 1
assert solution.checkPowersOfThree(3) == True # single power of three
assert solution.checkPowersOfThree(4) == True # 3 + 1
assert solution.checkPowersOfThree(5) == False # would require duplicate powers
assert solution.checkPowersOfThree(9) == True # exact power of three
assert solution.checkPowersOfThree(12) == True # example: 9 + 3
assert solution.checkPowersOfThree(21) == False # example with ternary digit 2
assert solution.checkPowersOfThree(91) == True # example: 81 + 9 + 1
assert solution.checkPowersOfThree(10) == True # 9 + 1
assert solution.checkPowersOfThree(13) == True # 9 + 3 + 1
assert solution.checkPowersOfThree(14) == False # contains ternary digit 2
assert solution.checkPowersOfThree(27) == True # larger exact power
assert solution.checkPowersOfThree(40) == True # 27 + 9 + 3 + 1
assert solution.checkPowersOfThree(10000000) == False # upper-bound stress test
| Test | Why |
|---|---|
n = 1 |
Smallest possible valid input |
n = 2 |
Cannot be formed with distinct powers |
n = 3 |
Single power of three |
n = 4 |
Sum of two distinct powers |
n = 5 |
Requires duplicate usage |
n = 9 |
Exact larger power |
n = 12 |
Provided example |
n = 21 |
Provided invalid example |
n = 91 |
Provided valid example |
n = 10 |
Non-consecutive powers |
n = 13 |
Multiple distinct powers |
n = 14 |
Contains ternary digit 2 |
n = 27 |
Another exact power |
n = 40 |
Combination of several powers |
n = 10000000 |
Large boundary stress test |
Edge Cases
One important edge case is when n itself is a power of three, such as 1, 3, 9, or 27. These numbers should immediately evaluate to true because they already consist of exactly one distinct power. The implementation handles this naturally because their ternary representation contains a single 1 digit and all remaining digits are 0.
Another important edge case occurs when the ternary representation contains a digit 2. For example, 21 becomes:
210
in base 3. The digit 2 means the algorithm would need two copies of the same power of three. A naive implementation that greedily subtracts powers without understanding the base representation could accidentally allow duplicates. The current implementation avoids this by directly checking every ternary digit.
A third important edge case involves very large inputs close to the upper constraint, such as 10^7. Recursive subset generation solutions may become inefficient or unnecessarily complicated. The mathematical solution remains efficient because it only processes logarithmically many ternary digits, roughly 15 iterations for the maximum input size.
A final subtle case is numbers like 2 or 5, which are close to valid sums but still impossible to represent using distinct powers. These cases ensure that the algorithm correctly rejects numbers requiring repeated powers. The ternary digit check handles these precisely and reliably.