[LeetCode][1780. Check if Number is a Sum of Powers of Three] 3 Solutions: Tricky, Recursion and Base 3 Convertion
By Long Luo
This article is the solution 3 Approaches: Tricky, Recursion and Base 3 Conversion of Problem 1780. Check if Number is a Sum of Powers of Three.
Here shows 3 Approaches to slove this problem: Tricky, Recursion and Base 3 Convertion.
Brute Froce
This method is tricky.
We can easy get a table that recorded all the numbers using between to .
Then scanning from the largest to the smallest, if find a value smaller or equal to , then subtract it from .
Repeat it until to .
1 | public static boolean checkPowersOfThree(int n) { |
Analysis
- Time Complexity:
- Space Complexity:
Base 3 Conversion
As the sum of distinct powers of , which means if we convert n to a base , every certain position can only be or .
1 | public static boolean checkPowersOfThree_base3(int n) { |
Analysis
- Time Complexity:
- Space Complexity:
Recursion
We can make our code more clean. Just One Line Is Enough!
1 | public static boolean checkPowersOfThree_rec(int n) { |
Analysis
- Time Complexity:
- Space Complexity:
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗