Problem

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4^x.

Examples

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Solution

Method 1 - Using Power of 2 and Mask 0x55555555

We know power of 4 should be power of 2 as well. So, we atleast need this:

return n > 0 && (n & (n-1)) == 0;

More on this: Power of Two.

But this is not enough. Lets look at binary number representation of some power of 4’s:

4  -> 100
16 -> 10000
64 -> 1000000

Note that the only ‘1’ bit should be locate at the odd location,for example,16.It’s binary is 00010000.So we can use ‘0x55555555’ to check if the ‘1’ bit is in the right place.

This is how 0x55555555 looks: 1010101010101010101010101010101.

So, to sum up, to check for power of 4, we need to check:

  1. Is number of power of 2? : num > 0 && (num&(num-1)) == 0
  2. Is the only bit on the odd position, by & operator

Code

Java
public boolean isPowerOfFour(int num) {
        return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;
}

Complexity

  • Time: O(log N)
  • Space: O(1)

It may be also possible to use other mask like 0x66666666.

Method 2 - Using Power of 2 and Check n-1 is Odd

This is again similar to previous solution.

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

Method 3 - Recursion

Code

Java
public boolean isPowerOfFour(int n) {
	
	if(n == 0) return false;
	if(n == 1) return true;
	
	if(n % 4 != 0) return false;
	
	return isPowerOfFour(n/4);    
}

Method 4 - Regex

The idea is that numbers in quaternary system that is power of 4 will be like 10, 100, 1000 and such. Similar to binary case. And this can be extended to any radix.

Code

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

Method 5 - Logarithm

Code

Java
public boolean isPowerOfFour(int num) {
	if(num <= 0) return false;
	double logValue = Math.log(num)/Math.log(4);
	return (logValue % 1) == 0 ;
}

Method 6 - Check Bitcounts and Trailing Zeroes

Code

Java
public boolean isPowerOfFour(int num) {
    return num>=1 && Integer.bitCount(num) == 1 && Integer.numberOfTrailingZeros(num)%2 == 0;
}