# How to solve Leetcode 342. Power of Four

## What is the bit representation of a power of four

### Problem statement

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`

.

#### Example 1

```
Input: n = 16
Output: true
```

#### Example 2

```
Input: n = 5
Output: false
```

#### Example 3

```
Input: n = 1
Output: true
```

#### Constraints

`-2^31 <= n <= 2^31 - 1`

.

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

### Solution 1: Division by four

#### Code

```
#include <iostream>
using namespace std;
bool isPowerOfFour(int n) {
while (n % 4 == 0 && n > 0) {
n /= 4;
}
return n == 1;
}
int main() {
cout << isPowerOfFour(16) << endl;
cout << isPowerOfFour(5) << endl;
cout << isPowerOfFour(1) << endl;
}
```

```
Output:
1
0
1
```

#### Complexity

Runtime:

`O(logn)`

.Extra space:

`O(1)`

.

### Solution 2: Binary representation

You can write down the binary representation of the powers of four to find the pattern.

```
1 : 1
4 : 100
16 : 10000
64 : 1000000
256 : 100000000
...
```

You might notice the patterns are **n is a positive integer having only one bit** `1`

in its binary representation and it is located at the odd positions (starting from the right).

How can you formulate those conditions?

If `n`

has only one bit `1`

in its binary representation `10...0`

, then `n - 1`

has the complete opposite binary representation `01...1`

.

You can use the bit operator AND to formulate this condition

```
n & (n - 1) == 0
```

Let `A`

be the number whose binary representation has only bits `1`

at all odd positions, then `n & A`

is never `0`

.

In this problem, `A < 2^31`

. You can choose`A = 0x55555555`

, the hexadecimal of `0101 0101 0101 0101 0101 0101 0101 0101`

.

#### Code

```
#include <iostream>
using namespace std;
bool isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}
int main() {
cout << isPowerOfFour(16) << endl;
cout << isPowerOfFour(5) << endl;
cout << isPowerOfFour(1) << endl;
}
```

```
Output:
1
0
1
```

#### Complexity

Runtime:

`O(1)`

.Extra space:

`O(1)`

.