# LeetCode 231: Power of Two

## Problem Restatement

We are given an integer `n`.

We need to determine whether `n` is a power of two.

That means we must check whether there exists an integer `x` such that:

$$
n = 2^x
$$

where:

```text
x >= 0
```

Examples of powers of two:

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

Examples that are not powers of two:

```text
3
5
6
12
18
```

LeetCode examples include:

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

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

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

The constraints allow signed 32-bit integers. ([leetcode.com](https://leetcode.com/problems/power-of-two/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | `True` if `n` is a power of two, otherwise `False` |
| Valid powers | `1, 2, 4, 8, 16, ...` |
| Negative numbers | Always `False` |

Function shape:

```python
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        ...
```

## Examples

Example 1:

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

Because:

$$
1 = 2^0
$$

Example 2:

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

Because:

$$
16 = 2^4
$$

Example 3:

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

Because no integer `x` satisfies:

$$
3 = 2^x
$$

Example 4:

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

Zero is not a power of two.

Example 5:

```text
Input:  n = -8
Output: false
```

Negative numbers are not powers of two.

## First Thought: Repeated Division

One direct approach is:

1. If `n <= 0`, return `False`.
2. While `n` is divisible by `2`, divide it by `2`.
3. If we finally reach `1`, return `True`.
4. Otherwise, return `False`.

Example:

```text
16 -> 8 -> 4 -> 2 -> 1
```

This works because every power of two can be repeatedly divided by two until reaching one.

Implementation:

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

        while n % 2 == 0:
            n //= 2

        return n == 1
```

This solution is correct, but there is an even cleaner bit manipulation approach.

## Key Insight

A power of two has exactly one `1` bit in binary representation.

Examples:

```text
1   = 0001
2   = 0010
4   = 0100
8   = 1000
16  = 10000
```

Every power of two contains:

```text
exactly one set bit
```

Now consider subtracting one.

Example:

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

Another:

```text
16      = 10000
16 - 1  = 01111
```

A power of two and one less than itself never share a `1` bit.

So:

$$
n \mathbin{\&} (n - 1) = 0
$$

for every positive power of two.

## Binary Visualization

Take:

```text
n = 8
```

Binary:

```text
1000
```

Now subtract one:

```text
0111
```

Bitwise AND:

```text
1000
0111
----
0000
```

Result:

```text
0
```

Now try a number that is not a power of two:

```text
n = 10
```

Binary:

```text
1010
```

Subtract one:

```text
1001
```

AND:

```text
1010
1001
----
1000
```

Result is not zero.

So `10` is not a power of two.

## Algorithm

1. If `n <= 0`, return `False`.
2. Compute:

$$
n \mathbin{\&} (n - 1)
$$

3. If the result is zero, return `True`.
4. Otherwise, return `False`.

## Correctness

Suppose `n` is a positive power of two.

Then its binary representation contains exactly one set bit.

For example:

```text
1000
```

Subtracting one flips that bit to `0` and turns all lower bits into `1`:

```text
0111
```

The two numbers share no set bits.

Therefore:

$$
n \mathbin{\&} (n - 1) = 0
$$

Now suppose `n` is positive but not a power of two.

Then its binary representation contains at least two set bits.

Subtracting one removes only the lowest set bit, so at least one set bit remains shared between `n` and `n - 1`.

Therefore:

$$
n \mathbin{\&} (n - 1) \neq 0
$$

Finally, numbers less than or equal to zero are never powers of two.

Therefore, the algorithm returns `True` exactly for positive powers of two.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | Only a few bit operations |
| Space | `O(1)` | No extra memory |

## Implementation

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

## Code Explanation

First we check:

```python
n > 0
```

because zero and negative numbers are invalid.

Then we use the binary property:

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

A positive integer satisfying this condition has exactly one set bit.

That means the number is a power of two.

## Alternative Approach: Count Bits

Another method is to count how many `1` bits appear in the binary representation.

A power of two has exactly one set bit.

Example:

```text
8  = 1000   -> one set bit
10 = 1010   -> two set bits
```

Python solution:

```python
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and bin(n).count("1") == 1
```

This is simpler conceptually, but slower and less elegant than direct bit manipulation.

## Testing

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

    assert s.isPowerOfTwo(1) is True
    assert s.isPowerOfTwo(2) is True
    assert s.isPowerOfTwo(4) is True
    assert s.isPowerOfTwo(16) is True
    assert s.isPowerOfTwo(1024) is True

    assert s.isPowerOfTwo(0) is False
    assert s.isPowerOfTwo(3) is False
    assert s.isPowerOfTwo(6) is False
    assert s.isPowerOfTwo(10) is False
    assert s.isPowerOfTwo(-8) is False

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `1` | Smallest power of two |
| `2`, `4`, `16` | Standard valid powers |
| `1024` | Larger valid power |
| `0` | Invalid boundary case |
| `3`, `6`, `10` | Non-powers |
| `-8` | Negative value |