LeetCode 1780: Check if Number is a Sum of Powers of Three Solution

Master LeetCode problem 1780 (Check if Number is a Sum of Powers of Three), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1780. Check if Number is a Sum of Powers of Three

Medium

Math

Problem Explanation

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)

Solution Code

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);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1780 (Check if Number is a Sum of Powers of Three)?

This page provides optimized solutions for LeetCode problem 1780 (Check if Number is a Sum of Powers of Three) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1780 (Check if Number is a Sum of Powers of Three)?

The time complexity for LeetCode 1780 (Check if Number is a Sum of Powers of Three) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1780 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1780 in Java, C++, or Python.

Back to LeetCode Solutions