Leetcode 326: Power of Three

In this Leetcode problem, we want to find out if an integer is a Power of 3.

Problem statement

The problem is easy enough to solve recursively:

if n = 0 then return false
if n = 1 then return true
if n = 3^p with p > 0, then n is divisible by 3 and n/3 = 3^(p-1)

For efficiency, we put these operations in a while loop, also it makes the algorithm O(1) in space. the algorithm O(log n) in time.

Here is the full code solution:

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

Happy coding!

What’s next:

• Checkout the solution for another problem: number of 1 bits
• Contact me: poitevinpm@gmail.com
• Looking to interview for a software engineer position? Contact me :)