Power of Four

Problem

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

Easy Brute Force: O(n)

public class Solution {
    public boolean isPowerOfFour(int num) {
        if (num >= 4) {
            while (num % 4 == 0) num /= 4;
        }
        return num == 1;
    }
}

Bit Representation: O(1)

public class Solution {
    public boolean isPowerOfFour(int num) {
        return Integer.toString(num, 4).matches("10*");
    }
}

Analysis

This problem cannot be solved by using max of 4's power % num == 0
Because 4 is not a prime, which means if given num = 2 it will wrongly return true
We need to find out if a given integer is a power of 4
The brute force solution is easy to come up and implement
However, we can also solve this problem by using Bit Regex
As long as the num is base 4, its 4-bit representation should start with "10"
We use Integer.toString(num, 4) to get the 4-bit representation
Then we call matches("10*") to get the result
Notice that when num = 1, calling "1".matches("10*") will return true