[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 \(\texttt{Math.power}(3, n)\) between \(1\) to \(10^7\).
Then scanning from the largest to the smallest, if find a value smaller or equal to \(n\), then subtract it from \(n\).
Repeat it until to \(0\).1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public static boolean checkPowersOfThree(int n) {
int[] nums = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969};
int idx = nums.length - 1;
while (idx >= 0 && n > 0) {
while (idx >= 0 && nums[idx] > n) {
idx--;
}
if (nums[idx] == n) {
return true;
}
n -= nums[idx];
idx--;
}
return false;
}
Analysis
- Time Complexity: \(O(1)\)
- Space Complexity: \(O(1)\)
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
2
3
4
5
6
7
8
9
10public static boolean checkPowersOfThree_base3(int n) {
while (n > 0) {
if (n % 3 == 2) {
return false;
}
n /= 3;
}
return true;
}
Analysis
- Time Complexity: \(O(logn)\)
- Space Complexity: \(O(1)\)
Recursion
We can make our code more clean. Just One Line Is Enough!1
2
3public static boolean checkPowersOfThree_rec(int n) {
return n < 2 || (n % 3 != 2 && checkPowersOfThree_rec(n / 3));
}
Analysis
- Time Complexity: \(O(logn)\)
- Space Complexity: \(O(1)\)
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. 😉😃💗