# LeetCode 1017: Convert to Base -2

## Problem Restatement

We are given a non-negative integer `n`.

We need to return its representation in base `-2` as a string (without leading zeros unless the answer is `"0"`).

In base `-2`, each digit is `0` or `1`, and the place values are `(-2)^0 = 1`, `(-2)^1 = -2`, `(-2)^2 = 4`, `(-2)^3 = -8`, and so on.

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | Non-negative integer `n` |
| Output | Base `-2` representation as a string |

Function shape:

```python
def baseNeg2(n: int) -> str:
    ...
```

## Examples

Example 1:

```python
n = 2
```

`2 = (-2)^2 + (-2)^1 + 0 = 4 - 2 = 2`. So representation is `"110"`.

Wait: `(-2)^2 = 4`, `(-2)^1 = -2`. So `110` means `1*4 + 1*(-2) + 0 = 2`. ✓

Answer:

```python
"110"
```

Example 2:

```python
n = 3
```

`3 = 4 + (-2) + 1 = (-2)^2 + (-2)^1 + (-2)^0`. So `"111"`.

Answer:

```python
"111"
```

Example 3:

```python
n = 4
```

`4 = (-2)^2 = 1 * 4`. So `"100"`.

Answer:

```python
"100"
```

## Key Insight

The conversion is similar to standard base conversion, but with base `-2`.

For each step:
1. `digit = n % 2` (always `0` or `1`, since we want non-negative remainders).
2. Append `digit` to the result (built in reverse).
3. `n = -(n // 2)` because dividing by `-2` flips the sign.

Or equivalently:

```python
digit = n & 1
n = -(n >> 1)
```

The bitwise trick works because `n >> 1` is floor division by `2`, and then we negate to account for the negative base.

## Algorithm

1. If `n == 0`, return `"0"`.
2. Build the representation bit by bit:
   - `digit = n % 2` (or `n & 1`)
   - `n = -(n // 2)` (or `-(n >> 1)`)
   - Prepend `digit` to the result.
3. Continue until `n == 0`.

## Correctness

This is a standard base conversion algorithm adapted for a negative base.

At each step, `digit` is the least significant bit of the current value in base `-2`. After extracting it, dividing by the base (and negating) shifts to the next position.

Because the base is `-2`, after dividing `n` by `2` (integer division) to remove the least significant place value, we negate to account for the sign change at each power.

## 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)` | Number of bits in `n` |
| Space | `O(log n)` | Storing the result |

## 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 baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"

        bits = []
        while n != 0:
            bits.append(str(n & 1))
            n = -(n >> 1)

        return "".join(reversed(bits))
```

## Code Explanation

Handle the zero case:

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

Extract bits from least significant to most significant:

```python
while n != 0:
    bits.append(str(n & 1))
    n = -(n >> 1)
```

`n & 1` gives the current bit. `-(n >> 1)` divides by `-2`.

Reverse the collected bits to get the most-significant-first representation:

```python
return "".join(reversed(bits))
```

## Testing

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

    assert s.baseNeg2(2) == "110"
    assert s.baseNeg2(3) == "111"
    assert s.baseNeg2(4) == "100"
    assert s.baseNeg2(0) == "0"
    assert s.baseNeg2(1) == "1"

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `2` | `"110"` | `4 + (-2) = 2` |
| `3` | `"111"` | `4 + (-2) + 1 = 3` |
| `4` | `"100"` | `(-2)^2 = 4` |
| `0` | `"0"` | Special case |
| `1` | `"1"` | `(-2)^0 = 1` |