# LeetCode 1073: Adding Negative Numbers

## Problem Restatement

We are given two arrays `arr1` and `arr2` representing two non-positive integers in base 10.

Each array has `-1` as the first element (sign) followed by the digits.

We need to return the sum of the two numbers, also in the same format.

The official constraints are similar to LeetCode 66 (Plus One) but for non-positive integers.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two arrays representing negative integers |
| Output | Array representing their sum |

Function shape:

```python
def addNegabinary(arr1: list[int], arr2: list[int]) -> list[int]:
    ...
```

## Note

This is actually **LeetCode 1073: Adding Negative Numbers** which asks to add two numbers in **negabinary** (base -2) representation.

## Problem Restatement (Corrected)

We are given two non-empty arrays `arr1` and `arr2` representing two numbers in base -2 (negabinary).

Each array has digits in most-significant-first order.

Return the sum in negabinary representation (no leading zeros except `[0]`).

## Examples

Example 1:

```python
arr1 = [1, 1, 1, 1, 1]
arr2 = [1, 0, 1]
```

`arr1` = `11111` in base -2 = `11`.

`arr2` = `101` in base -2 = `5`.

Sum = `16` = `10000` in base -2 = `[1, 0, 0, 0, 0]`.

Answer:

```python
[1, 0, 0, 0, 0]
```

## Key Insight

Add digit by digit from least significant to most significant, maintaining a carry. The carry in negabinary can be 0 or -1 (since carrying from position `k` removes `(-2)^k` and adds `(-2)^(k+1)/(-2)`).

When `digit_sum = digit1 + digit2 + carry`:
- The current output bit is `digit_sum & 1`, which is always `0` or `1`.
- The carry for the next position is `-(digit_sum // 2)`.

## 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.

## 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 addNegabinary(self, arr1: list[int], arr2: list[int]) -> list[int]:
        i, j = len(arr1) - 1, len(arr2) - 1
        carry = 0
        result = []

        while i >= 0 or j >= 0 or carry:
            val = carry
            if i >= 0:
                val += arr1[i]
                i -= 1
            if j >= 0:
                val += arr2[j]
                j -= 1

            result.append(val & 1)
            carry = -(val >> 1)

        while len(result) > 1 and result[-1] == 0:
            result.pop()

        return result[::-1]
```

## Testing

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

    assert s.addNegabinary([1,1,1,1,1], [1,0,1]) == [1,0,0,0,0]
    assert s.addNegabinary([0], [0]) == [0]
    assert s.addNegabinary([0], [1]) == [1]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| `11111 + 101` | `[1,0,0,0,0]` | `11 + 5 = 16` in negabinary |
| `0 + 0` | `[0]` | Zero |
| `0 + 1` | `[1]` | One |