342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

Solution:

If a number is power of four, it must be power of two.

If a number is power of two, it only has one 1 in binary representation.

If a number is power of four, it minus 1 can be divided by 3.

Let's say 4ⁿ-1 = (2ⁿ+1) x (2ⁿ - 1).

Any three consecutive number, there must be one that can be divided by 3.

So in 2ⁿ + 1, 2ⁿ, 2ⁿ - 1, we know 2ⁿ cannot be divided by 3.

Therefore, either 2ⁿ + 1 or 2ⁿ - 1 can be divided by 3.



Code:

public class Solution {
    public boolean isPowerOfFour(int num) {
        return num > 0 && (num & (num - 1)) == 0 && (num - 1) % 3 == 0;
    }
}