[Leetcode][1780. Check if Number is a Sum of Powers of Three] 3 Solutions: Tricky, Recursive and Base 3 convertion
By Long Luo
This article is the solution of Problem 1780. Check if Number is a Sum of Powers of Three.
Brute Froce
This method is tricky.
We can easy get a table that recorded all the numbers using Math.power(3, n) 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 3, which means if we convert n to a base 3, every certain position can only be 0 or 1.
1 | public static boolean checkPowersOfThree_base3(int n) { |
Analysis
- Time Complexity:
- Space Complexity:
Recursive
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. 😉😃💗