DEV Community

loading...
Cover image for Solution: Power of Three

Solution: Power of Three

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・3 min read

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
};
Enter fullscreen mode Exit fullscreen mode
w/ Modulo:
var isPowerOfThree = function(n) {
    return n > 0 && 1162261467 % n === 0
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
w/ Modulo:
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode
w/ Modulo:
class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode
w/ Modulo:
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (1)

Collapse
rohithv07 profile image
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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Leetcode Daily Challenge + Other resources

Forem Open with the Forem app