# Power of Four Leetcode Solution

Difficulty Level Easy
Frequently asked in Two Sigma
algorithms Bit Manipulation coding Interview interviewprep LeetCode LeetCodeSolutions MathViews 3220

## Problem Statement

We are given an integer and we have to check if the number is power of 4 or not. A number is power of 4 if there exist an integer a such that,  num= 4^a.

`16`
`true`
`5`
`false`

## Approach 1 (Brute Force)

An obvious way to check if a number is power of 4 or not is to remove all the fators of 4 by repeatedly dividing the number by 4 untill it is divisible by 4. And check finally if the remaining number is equal to 1 or not. If it is 1 then its obvious that there is no any factor other than 4, hence the number was power of 4. If it is not 1 then the number is not power of 4.

### Implementation for Power of Four Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

bool isPowerOfFour(int n)
{
if (n == 0) return false;

while (n % 4 == 0) n /= 4;

if(n==1) return true;
else return false;
}

int main()
{
int n=16;

if(isPowerOfFour(16)) cout<<"true"<<endl;
else cout<<"false"<<endl;

return 0;
}```
`true`

#### Java Program

```import java.util.*;
class Rextester{

public static boolean isPowerOfFour(int n)
{
if (n == 0) return false;

while (n % 4 == 0) n /= 4;

if(n==1) return true;
else return false;

}

public static void main(String args[])
{
int n=16;
System.out.println(isPowerOfFour(n));
}
}
```
`true`

### Complexity Analysis for Power of Four Leetcode Solution

#### Time Complexity

O(logN) : We are dividing the given number by 4 each time. Therefore in worst case the loop will run logN (base 4) times. Hence we can say time complexity is O(logN).

#### Space Complexity

O(1) : No extra memory is used.

## Approach 2 (Precomputation)

We know there will be very limited numbers in an integer(32-bit) range which is power of 4. How ?
Lets see:

We have been given an integer x, therefore    :   x <= 2^31-1
So maximum power of 4 in this range will be:   log4(2^31-1) = 15

Now we can easily store these 15 numbers by doing precomputation.
Therefore we can now find for every number in constant time whether it is a power of 4 or not.

### Implementation for Power of Four Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

set<int> nums;

bool isPowerOfFour(int n)
{
return nums.count(n);
}

int main()
{
int n=15;
int x = 1;
nums.insert(x);
for (int i = 1; i < n + 1; ++i)
{
x = x * 4;
nums.insert(x);
}

if(isPowerOfFour(16)) cout<<"true"<<endl;
else cout<<"false"<<endl;

return 0;
}```
`true`

#### Java Program

```import java.util.*;
class Rextester{

static int n = 15;
static List<Integer> nums = new ArrayList<Integer>();
static{
int x = 1;
for (int i = 1; i < n + 1; ++i)
{
x = x * 4;
}
}

public static boolean isPowerOfFour(int n)
{
return nums.contains(n);
}

public static void main(String args[])
{
int n=16;
System.out.println(isPowerOfFour(n));
}
}
```
`true`

### Complexity Analysis for Power of Four Leetcode Solution

#### Time Complexity

O(1) : We have all numbers which are power of 4 stored in our program. Hence we can search for a given number and return true or false in constant time.

#### Space Complexity

O(1) : For 32-bit Integer input only 15 numbers are stored in the memory i.e. constant space or O(1).

## Approach 3 (Bit manipulation)

Using bit manipulation we can solve this problem very efficiently.
We know for a number to be power of 4, it needs to be power of 2 also. We have already discussed the condition for a number to be power of 2 in Power of Two Leetcode Solution using bit manipulation.

So let’s first check if number is a power of two: x > 0 and x & (x – 1) == 0.
Now we can analyse that if the number is even power of 2 then it will be power of 4, and if the number is odd power of 2 then it will not be power of 4.
In binary representation this number will contain only single 1-bit at even position (power of 4) or at odd position (not power of 4).

Hence if we do bitwise and of a number(power of 4) with number(101010….10)(base 2) the result will be zero.
We can apply above concept by writing second number in hexadecimal as (aaaaaaaa)(base 16).

### Implementation for Power of Four Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

bool isPowerOfFour(int n)
{
return (n > 0)  &&  ((n & (n-1)) == 0)  && ((n & 0xaaaaaaaa) == 0) ;
}

int main()
{
if(isPowerOfFour(16)) cout<<"true"<<endl;
else cout<<"false"<<endl;

return 0;
}```
`true`

#### Java Program

```import java.util.*;
class Rextester{

public static boolean isPowerOfFour(int n)
{
return (n > 0)  &&  ((n & (n-1)) == 0)  && ((n & 0xaaaaaaaa) == 0) ;
}

public static void main(String args[])
{
int n=16;
System.out.println(isPowerOfFour(n));
}
}
```
`true`

### Complexity Analysis for Power of Four Leetcode Solution

#### Time Complexity

O(1) : Bitwise and is a constant operation.

#### Space Complexity

O(1) : Constant space.

## Approach 4 (Bit Manipulation + Maths)

We know that if a number is power of 4 then it will be even power of 2. Considering both cases for x=2^a :
a=2k or a=2k+1

If we divide these two numbers by 3 we will get remainder as following :
2^2k mod 3 = 4^k mod 3 = (3+1)^k mod 3 = 1
2^(2k+1) mod 3 = 2×4^k mod 3 = 2×(3+1)^k mod 3 = 2

Hence final condition for a number to be power of 4 should be :

x is power of 2 and x % 3 == 1

### Implementation for Power of Four Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

bool isPowerOfFour(int n)
{
return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
}

int main()
{
if(isPowerOfFour(16)) cout<<"true"<<endl;
else cout<<"false"<<endl;

return 0;
}```
`true`

#### Java Program

```import java.util.*;
class Rextester{

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

public static void main(String args[])
{
int n=16;
System.out.println(isPowerOfFour(n));
}
}
```
`true`

### Complexity Analysis for Power of Four Leetcode Solution

#### Time Complexity

O(1) : Constant time.

#### Space Complexity

O(1) : Constant space.

Translate »