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.

Leetcode Problem #326 (Easy): Power of Three

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?

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