Description
Given an integer n, return true if it is a power of three. Otherwise, return false.
An integer n is a power of three, if there exists an integer x such that n == 3x.
Example 1:
Input: n = 27
Output: true
Explanation: 27 = 33
Example 2:
Input: n = 0
Output: false
Explanation: There is no x where 3x = 0.
Example 3:
Input: n = -1
Output: false
Explanation: There is no x where 3x = (-1).
Constraints:
Follow up: Could you solve it without loops/recursion?
Solutions
Solution 1: Trial Division
If n \gt 2, we can continuously divide n by 3. If it's not divisible, it means n is not a power of 3, otherwise we continue dividing by 3 until n is less than or equal to 2. If n equals 1, it means n is a power of 3, otherwise it's not a power of 3.
Time complexity O(log_3n), space complexity O(1).
PythonJavaC++GoTypeScriptRustJavaScript
class Solution:
def isPowerOfThree(self, n: int) -> bool:
while n > 2:
if n % 3:
return False
n //= 3
return n == 1(code-box)
class Solution {
public boolean isPowerOfThree(int n) {
while (n > 2) {
if (n % 3 != 0) {
return false;
}
n /= 3;
}
return n == 1;
}
}(code-box)
class Solution {
public:
bool isPowerOfThree(int n) {
while (n > 2) {
if (n % 3) {
return false;
}
n /= 3;
}
return n == 1;
}
};(code-box)
func isPowerOfThree(n int) bool {
for n > 2 {
if n%3 != 0 {
return false
}
n /= 3
}
return n == 1
}(code-box)
function isPowerOfThree(n: number): boolean {
while (n > 2) {
if (n % 3 !== 0) {
return false;
}
n = Math.floor(n / 3);
}
return n === 1;
}(code-box)
impl Solution {
pub fn is_power_of_three(mut n: i32) -> bool {
while n > 2 {
if n % 3 != 0 {
return false;
}
n /= 3;
}
n == 1
}
}(code-box)
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfThree = function (n) {
while (n > 2) {
if (n % 3 !== 0) {
return false;
}
n = Math.floor(n / 3);
}
return n === 1;
};(code-box)
Solution 2: Mathematics
If n is a power of 3, then the maximum value of n is 3^{19} = 1162261467. Therefore, we only need to check if n is a divisor of 3^{19}.
Time complexity O(1), space complexity O(1).
PythonJavaC++GoTypeScriptRustJavaScript
class Solution:
def isPowerOfThree(self, n: int) -> bool:
return n > 0 and 1162261467 % n == 0(code-box)
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}(code-box)
class Solution {
public:
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
};(code-box)
func isPowerOfThree(n int) bool {
return n > 0 && 1162261467%n == 0
}(code-box)
function isPowerOfThree(n: number): boolean {
return n > 0 && 1162261467 % n == 0;
}(code-box)
impl Solution {
pub fn is_power_of_three(mut n: i32) -> bool {
n > 0 && 1162261467 % n == 0
}
}(code-box)
/**
* @param {number} n
* @return {boolean}
*/
var isPowerOfThree = function (n) {
return n > 0 && 1162261467 % n == 0;
};(code-box)
