DEV Community is a community of 636,824 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Solution: Power of Three

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.

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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 == 3^x`.

Follow up: Could you solve it without loops/recursion?

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:

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:

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:

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:

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;
}
};
``````

Discussion (1)

Rohith V

Here is my attempt on this problem :

``````class Solution {
public boolean isPowerOfThree(int n) {
if (n == 0)
return false;
return (Math.log10(n) / Math.log10(3)) % 1 == 0;
}
}
``````

Leetcode Daily Challenge + Other resources