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 <= 107This 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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log3n), as we are dividing n by 3 each step.
Space Complexity: O(1), no additional space is used.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: Exponential, due to exploring all combinations.
Space Complexity: O(n) for the recursion stack.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(log3n), as we are dividing |
| Backtracking Approach | Time Complexity: Exponential, due to exploring all combinations. |
Check if Number is a Sum of Powers of Three - Leetcode 1780 - Python • NeetCodeIO • 10,215 views views
Watch 9 more video solutions →Practice Check if Number is a Sum of Powers of Three with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor