This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #326 (Easy): Power of Three
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given an integer
n, returntrueif it is a power of three. Otherwise, returnfalse.An integer
nis a power of three, if there exists an integerxsuch thatn == 3^x.Follow up: Could you solve it without loops/recursion?
Examples:
Example 1: Input: n = 27 Output: true
Example 2: Input: n = 0 Output: false
Example 3: Input: n = 9 Output: true
Example 4: Input: n = 45 Output: false
Constraints:
-2^31 <= n <= 2^31 - 1
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
The naive approach here would be to simply iterate through dividing n by 3 to see if we ultimately get to 1. But if we want to accomplish this solution without iteration or recursion, we'll have to get creative.
Approach 1: Logarithms -
We can take advantage of the natural mathematical properties of logarithms to find our solution. If n is a power of 3, then 3^x = n. This can be rewritten as log3 n = x, where x will be an integer if n is a power of 3.
Since most programming languages can't natively do log3 calculations, we can take advantage of another property of logarithms: log3 n can be rewritten as log n / log 3. This will produce a slight amount of floating point error, but any value that is within a close margin (1e-10) while n is constrained to an int will be a correct.
Approach 2: Modulo -
Since 3 is a prime number, any power of 3 will only be divisible by any power of 3 that is equal or smaller. We can use this to our advantage by taking the largest possible power of 3 within our constraints (3^19) and performing a modulo n operation on it. If the result is a 0, then n is a power of 3.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
w/ Logarithms:
var isPowerOfThree = function(n) {
let a = Math.log(n) / Math.log(3)
return Math.abs(a - Math.round(a)) < 1e-10
};
w/ Modulo:
var isPowerOfThree = function(n) {
return n > 0 && 1162261467 % n === 0
};
Python Code:
(Jump to: Problem Description || Solution Idea)
w/ Logarithms:
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n < 1: return False
ans = log(n, 3)
return abs(ans - round(ans)) < 1e-10
w/ Modulo:
class Solution:
def isPowerOfThree(self, n: int) -> bool:
return n > 0 and 1162261467 % n == 0
Java Code:
(Jump to: Problem Description || Solution Idea)
w/ Logarithms:
class Solution {
public boolean isPowerOfThree(int n) {
double a = Math.log(n) / Math.log(3);
return Math.abs(a - Math.round(a)) < 1e-10;
}
}
w/ Modulo:
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
w/ Logarithms:
class Solution {
public:
bool isPowerOfThree(int n) {
double a = log(n) / log(3);
return abs(a - round(a)) < 1e-10;
}
};
w/ Modulo:
class Solution {
public:
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-04-27T08:11:18+00:00) Solution: Power of Three. Retrieved from https://www.scien.cx/2021/04/27/solution-power-of-three/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.