# LeetCode 1009: Complement of Base 10 Integer

## Problem Restatement

The complement of an integer is obtained by flipping all its bits.

For example, the decimal number `5` is `101` in binary. Its complement is `010`, which is `2`.

We are given an integer `n` and need to return its complement.

Note: the complement does not flip leading zeros (only the bits in the binary representation of `n` count).

The official constraints state that `0 <= n < 10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Non-negative integer `n` |
| Output | Complement of `n` |
| Rule | Flip all bits in the binary representation of `n` |

Function shape:

```python
def bitwiseComplement(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 5
```

Binary: `101`. Complement: `010 = 2`.

Answer:

```python
2
```

Example 2:

```python
n = 7
```

Binary: `111`. Complement: `000 = 0`.

Answer:

```python
0
```

Example 3:

```python
n = 10
```

Binary: `1010`. Complement: `0101 = 5`.

Answer:

```python
5
```

## Key Insight

To flip all bits in the binary representation of `n`, XOR `n` with a mask of all `1`s of the same bit length.

The mask is `2^bit_length - 1`, where `bit_length` is the number of bits in `n`.

Special case: `n = 0` has no bits to flip, and the complement is `1`.

## Algorithm

1. If `n == 0`, return `1`.
2. Compute the bit length of `n`.
3. Create a mask: `(1 << bit_length) - 1`.
4. Return `n XOR mask`.

## Correctness

XORing with a mask of all `1`s flips every bit. The mask has exactly the same number of bits as `n`, so only the bits in `n`'s representation are flipped. No leading zeros are introduced.

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log n)` | Computing bit length |
| Space | `O(1)` | Constant extra space |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1
        bit_length = n.bit_length()
        mask = (1 << bit_length) - 1
        return n ^ mask
```

## Code Explanation

Handle the zero case:

```python
if n == 0:
    return 1
```

Compute the number of bits:

```python
bit_length = n.bit_length()
```

Build the mask of all `1`s:

```python
mask = (1 << bit_length) - 1
```

For example, if `n = 5` (`101`), `bit_length = 3`, `mask = 7` (`111`).

XOR with the mask flips all bits:

```python
return n ^ mask
```

`5 ^ 7 = 101 ^ 111 = 010 = 2`.

## Testing

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

    assert s.bitwiseComplement(5) == 2
    assert s.bitwiseComplement(7) == 0
    assert s.bitwiseComplement(10) == 5
    assert s.bitwiseComplement(0) == 1
    assert s.bitwiseComplement(1) == 0

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `5` | `2` | `101 → 010` |
| `7` | `0` | `111 → 000` |
| `10` | `5` | `1010 → 0101` |
| `0` | `1` | Special case |
| `1` | `0` | `1 → 0` |