Leetcode 342: Powers of 4

In this Leetcode problem, we are given an integer and must decide if it is a power of 4 or not.

Problem statement

This is a very similar problem with Powers of 2 and Powers of 3 solution, we can find a solution by noticing that a power of 4 has a binary representation of a single 1 bit followed by 2p 0s with p >= 0.

100000000000000
 -- 2p zeros --

Therefore n is a power of 4 if and only if:

• n == 1
• OR n is divisible by 4 and n/4 is a power of 4

In binary terms we write n /= 4 with n >>= 2 and with test that n is divisible by 4 with n & 3 == 0 (binary representation of 3 is 11).

Here is the full code:

class Solution {
    public boolean isPowerOfFour(int num) {
        if (num == 0) {
            return false;
        }
        while ((num & 3) == 0) {
            num >>= 2;
        }
        return (num == 1);
    }
}

I used a while loop instead of recursion for effectiveness. The space complexity is O(1) and the time complexity is O(log num).

Happy coding!

What’s next:

• Checkout the solution for another problem: Apply discount every n orders
• Contact me: poitevinpm@gmail.com
• Looking to interview for a software engineer position? Contact me :)