🎨Now live: Try our Free AI Image Generation Feature

Description
The task is to determine whether a given integer n
is a power of three. A number is considered a power of three if it can be written as (3^k), where (k) is a non-negative integer.
Intuition
Powers of three grow exponentially, meaning they increase very quickly as the exponent increases. Since there is a limited range of integers that we need to check (from (3^0) to (3^{30}), since (3^{31}) exceeds the maximum value of a typical 32-bit integer), we can iterate through these powers and see if any of them match n
.
Approach
- Iteration through Powers:
- Start from (3^0) and calculate powers of 3 incrementally.
- For each power, check if it equals
n
. - If a match is found, returntrue
. If no match is found by the time you reach (3^{30}), returnfalse
. - Edge Cases: Handle cases where
n
is less than 1, as negative numbers and zero can never be powers of three.
Complexity
Time Complexity:
- The loop runs up to 31 times (since the largest possible power of three within the 32-bit integer range is (3^{30})).
- Therefore, the time complexity is (O(1)), as it has a constant number of iterations.
Space Complexity:
- We only use a few variables, so the space complexity is (O(1)).
Code
C++
class Solution {
public:
bool isPowerOfThree(int n) {
for (int i = 0; i < 31; i++) {
long long pow = powl(3, i);
if (pow == n) {
return true;
}
}
return false;
}
};
Python
class Solution:
def isPowerOfThree(self, n: int) -> bool:
for i in range(31):
if 3 ** i == n:
return True
return False
Java
class Solution {
public boolean isPowerOfThree(int n) {
for (int i = 0; i < 31; i++) {
double pow = Math.pow(3, i);
if (pow == n) {
return true;
}
}
return false;
}
}
JavaScript
var isPowerOfThree = function(n) {
for(let i=0;i<31;i++){
let pow=Math.pow(3,i)
if(pow===n){
return true
}
}
return false
};