# LeetCode 342: Power of Four

## Problem Restatement

We are given an integer `n`.

Return `true` if `n` is a power of four. Otherwise return `false`.

A number is a power of four if there exists an integer `x` such that:

```text
n = 4^x
```

Examples:

```text
1  = 4^0
4  = 4^1
16 = 4^2
64 = 4^3
```

are powers of four.

The official problem asks whether `n` is a power of four and includes a follow-up asking for a solution without loops or recursion. ([leetcode.com](https://leetcode.com/problems/power-of-four/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | `true` if `n` is a power of four |
| Valid form | `n = 4^x` for some integer `x >= 0` |

Function shape:

```python
def isPowerOfFour(n: int) -> bool:
    ...
```

## Examples

Example 1:

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

Because:

```text
16 = 4^2
```

Example 2:

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

There is no integer `x` such that:

```text
4^x = 5
```

Example 3:

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

Because:

```text
1 = 4^0
```

## First Thought: Repeated Division

A direct approach is:

1. While `n` is divisible by `4`:
   1. Divide `n` by `4`.
2. At the end, check whether `n == 1`.

```python
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False

        while n % 4 == 0:
            n //= 4

        return n == 1
```

This works, but the follow-up asks for a constant-time bit solution.

## Key Insight

A power of four is also a power of two.

So first check whether `n` has exactly one set bit.

For powers of two:

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

Examples:

| Number | Binary |
|---|---|
| `1` | `0001` |
| `2` | `0010` |
| `4` | `0100` |
| `8` | `1000` |

Subtracting `1` flips all bits after the single set bit.

Example:

```text
8      = 1000
8 - 1  = 0111
AND    = 0000
```

But powers of two are not enough.

For example:

```text
8 = 2^3
```

is not a power of four.

So we need another property.

## Binary Pattern of Powers of Four

Powers of four have their single `1` bit at even bit positions.

Examples:

| Number | Binary | Set bit position |
|---|---|---|
| `1` | `0001` | 0 |
| `4` | `0100` | 2 |
| `16` | `00010000` | 4 |
| `64` | `01000000` | 6 |

All are even positions.

The hexadecimal mask:

```text
0x55555555
```

has binary form:

```text
01010101010101010101010101010101
```

It keeps only even-position bits.

So a number is a power of four if:

1. `n > 0`
2. `n` is a power of two
3. Its set bit is in an even position

The third condition is:

```text
n & 0x55555555 != 0
```

## Algorithm

Return whether all three conditions hold:

```python
n > 0
and n & (n - 1) == 0
and n & 0x55555555 != 0
```

## Walkthrough

Use:

```text
n = 16
```

Binary:

```text
16 = 00010000
```

Check positivity:

```text
16 > 0
```

true.

Check power of two:

```text
16 & 15
00010000
00001111
--------
00000000
```

So `16` has exactly one set bit.

Check even-position mask:

```text
16 & 0x55555555 != 0
```

The set bit survives because it is at position `4`, which is even.

Return `True`.

Now use:

```text
n = 8
```

Binary:

```text
8 = 00001000
```

It passes the power-of-two check.

But its set bit is at position `3`, which is odd.

So:

```text
8 & 0x55555555 == 0
```

Return `False`.

## Correctness

If the algorithm returns `true`, then:

1. `n > 0`
2. `n & (n - 1) == 0`
3. `n & 0x55555555 != 0`

The second condition means `n` has exactly one set bit, so `n` is a power of two.

The third condition means that set bit is located at an even bit position.

Powers of four are exactly the powers of two whose single set bit appears at positions:

```text
0, 2, 4, 6, ...
```

Therefore `n` must equal:

```text
4^x
```

for some nonnegative integer `x`.

Now suppose `n` is a power of four.

Then `n` is positive.

Its binary representation contains exactly one set bit, so:

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

Also, powers of four place that bit at an even position, so:

```text
n & 0x55555555 != 0
```

Therefore all three conditions hold, and the algorithm returns `true`.

So the algorithm returns `true` exactly for powers of four.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | Constant number of bit operations |
| Space | `O(1)` | No extra data structures |

## Implementation

```python
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return (
            n > 0
            and (n & (n - 1)) == 0
            and (n & 0x55555555) != 0
        )
```

## Code Explanation

First check positivity:

```python
n > 0
```

Negative numbers and zero cannot be powers of four.

Then check whether `n` is a power of two:

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

This ensures there is exactly one set bit.

Finally check whether that bit is in an even position:

```python
(n & 0x55555555) != 0
```

The mask keeps only bits at positions:

```text
0, 2, 4, 6, ...
```

If all conditions are true, `n` is a power of four.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isPowerOfFour(1) == True
    assert s.isPowerOfFour(4) == True
    assert s.isPowerOfFour(16) == True
    assert s.isPowerOfFour(64) == True

    assert s.isPowerOfFour(2) == False
    assert s.isPowerOfFour(8) == False
    assert s.isPowerOfFour(5) == False
    assert s.isPowerOfFour(0) == False
    assert s.isPowerOfFour(-4) == False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `1` | Smallest power of four |
| `4`, `16`, `64` | Standard powers of four |
| `2`, `8` | Powers of two but not four |
| `5` | Random non-power |
| `0` | Zero case |
| `-4` | Negative number |