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