1780. Check if Number is a Sum of Powers of Three
Explanation
To solve this problem, we can iterate over the powers of three starting from the highest power less than or equal to n. At each step, we check if we can include the current power of three in the sum to reach the target number n. We do this by subtracting the current power of three from n and recursively checking if the remaining number can be represented as a sum of powers of three. If we can represent n as a sum of distinct powers of three, we return true, otherwise false.
Algorithm:
- Start from the highest power of three less than or equal to n.
- Subtract the current power of three from n.
- Recursively check if the remaining number can be represented as a sum of powers of three.
- If n becomes 0, return true as we have found a valid representation.
- If n becomes negative or we reach the smallest power of three, return false.
- Repeat the process for all powers of three less than or equal to n.
Time Complexity: O(log n)
Space Complexity: O(log n)
class Solution {
public boolean checkPowersOfThree(int n) {
return checkPowersOfThreeHelper(n, 1);
}
private boolean checkPowersOfThreeHelper(int n, int pow) {
if (n == 0) {
return true;
}
if (n < 0 || pow > n) {
return false;
}
return checkPowersOfThreeHelper(n - pow, pow * 3) || checkPowersOfThreeHelper(n, pow * 3);
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.