Check if Number is a Sum of Powers of Three - Solution & Explanation
Problem Statement
Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.
An integer y is a power of three if there exists an integer x such that y == 3x.
Example 1:
Input: n = 12 Output: true Explanation: 12 = 31 + 32
Example 2:
Input: n = 91 Output: true Explanation: 91 = 30 + 32 + 34
Example 3:
Input: n = 21 Output: false
Constraints:
1 <= n <= 107
Approach Overview
Problem Overview: You receive an integer n. The task is to determine whether it can be represented as the sum of distinct powers of three (for example 1, 3, 9, 27...). Each power can be used at most once. The problem reduces to checking whether a combination of these powers adds exactly to n.
Approach 1: Greedy / Base-3 Representation (Time: O(log3 n), Space: O(1))
The key observation: powers of three behave like digits in base-3 representation. If n can be written as a sum of distinct powers of three, then its base-3 representation must contain only digits 0 or 1. A digit 2 would mean the same power of three is used twice, which violates the constraint. Convert the number by repeatedly dividing n by 3 and checking the remainder. If any remainder equals 2, return false. Otherwise continue until n becomes zero. This greedy observation avoids generating combinations entirely and runs in logarithmic time. The approach relies purely on number properties from math and is the optimal solution expected in interviews.
Approach 2: Backtracking Over Powers (Time: O(2k), Space: O(k))
Another way to think about the problem is as a subset-sum over powers of three. First generate powers of three up to n (for example 1, 3, 9, 27...). Then recursively try including or excluding each power while subtracting from the remaining target. If the remaining value reaches 0, a valid combination exists. If it becomes negative or you exhaust all powers, that branch fails. This approach uses recursion and explores the decision tree of subsets, which is why the complexity becomes exponential in the number of powers (k ≈ log3 n). It demonstrates the brute-force reasoning behind the problem and uses techniques from backtracking and recursion.
Recommended for interviews: The greedy base-3 check is the expected solution. Interviewers want to see the insight that the sum of distinct powers of three corresponds directly to base-3 digits restricted to 0 and 1. Implementing the greedy division loop shows strong mathematical reasoning and yields O(log n) time with constant space. The backtracking approach is still useful to discuss because it shows how the problem maps to subset selection before the mathematical shortcut is recognized.
Approach 1: Greedy Approach
This approach involves checking if the remainder when dividing by 3 is other than 0 or 1, and subtracting the corresponding power of three if it is 1. Repeat this until the number reduces to zero or we find a remainder that isn't suitable.
This code checks the remainder of n when divided by 3 in each step. If any remainder is 2, it's impossible to form n using powers of three. We divide n by 3 iteratively until n becomes zero.
Complexity
Time Complexity: O(log3n), as we are dividing n by 3 each step.
Space Complexity: O(1), no additional space is used.
Approach 2: Backtracking Approach
This approach uses recursion to try all combinations of the power of threes by backtracking. It searches incrementally and backs out when a wrong path is reached.
The C solution uses a recursive function isSum to traverse every power of three up from 0, using decision trees to include or exclude each power.
Complexity
Time Complexity: Exponential, due to exploring all combinations.
Space Complexity: O(n) for the recursion stack.
Approach 3: Mathematical Analysis
We find that if a number n can be expressed as the sum of several "different" powers of three, then in the ternary representation of n, each digit can only be 0 or 1.
Therefore, we convert n to ternary and then check whether each digit is 0 or 1. If not, then n cannot be expressed as the sum of several powers of three, and we directly return false; otherwise, n can be expressed as the sum of several powers of three, and we return true.
The time complexity is O(log_3 n), and the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(log3n), as we are dividing |
| Backtracking Approach | Time Complexity: Exponential, due to exploring all combinations. |
| Mathematical Analysis | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy / Base-3 Representation | O(log n) | O(1) | Best general solution. Uses number properties to check digits in base-3. |
| Backtracking Over Powers | O(2^k), k ≈ log3(n) | O(k) | Useful for understanding the subset-sum formulation or during initial brute-force reasoning. |
Video Solution
Check if Number is a Sum of Powers of Three - Leetcode 1780 - Python • NeetCodeIO • 11,231 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if Number is a Sum of Powers of Three easy or hard?
Check if Number is a Sum of Powers of Three Python/Java solution
How to solve Check if Number is a Sum of Powers of Three in O(log n)?
What is the best approach for Check if Number is a Sum of Powers of Three?
Is Check if Number is a Sum of Powers of Three asked at Google/Amazon/Meta?
What data structure is used in Check if Number is a Sum of Powers of Three?
What is the time complexity of Check if Number is a Sum of Powers of Three?
Ready to solve this problem?
Practice Check if Number is a Sum of Powers of Three with our built-in code editor and test cases.
Practice on FleetCode