# Adding Two Negabinary Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/adding-two-negabinary-numbers)
Canonical: https://scaleengineer.com/dsa/problems/adding-two-negabinary-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Grab](https://scaleengineer.com/companies/grab)
---
## Problem
Given two numbers `arr1` and `arr2` in base **\-2**, return the result of adding them together.

Each number is given in _array format_: as an array of 0s and 1s, from most significant bit to least significant bit. For example, `arr = [1,1,0,1]` represents the number `(-2)^3 + (-2)^2 + (-2)^0 = -3`. A number `arr` in _array, format_ is also guaranteed to have no leading zeros: either `arr == [0]` or `arr[0] == 1`.

Return the result of adding `arr1` and `arr2` in the same format: as an array of 0s and 1s with no leading zeros.

**Example 1:**

**Input:** arr1 = [1,1,1,1,1], arr2 = [1,0,1]
**Output:** [1,0,0,0,0]
**Explanation:** arr1 represents 11, arr2 represents 5, the output represents 16.

**Example 2:**

**Input:** arr1 = [0], arr2 = [0]
**Output:** [0]

**Example 3:**

**Input:** arr1 = [0], arr2 = [1]
**Output:** [1]

**Constraints:**

* `1 <= arr1.length, arr2.length <= 1000`
* `arr1[i]` and `arr2[i]` are `0` or `1`
* `arr1` and `arr2` have no leading zeros

# Approaches
## Convert to Decimal, Add, and Convert Back
This approach follows a straightforward, multi-step process. First, it converts the two negabinary numbers from their array format into standard base-10 (decimal) integers. Since the values can become very large, `java.math.BigInteger` is used to prevent overflow. After conversion, the two decimal numbers are added together. Finally, the resulting sum is converted from its decimal representation back into the negabinary array format.
**Time:** O((max(N, M))^2). The conversion steps involve loops where `BigInteger` multiplication and division are performed. These operations are not constant time; their complexity depends on the number of bits in the operands, which is proportional to the array lengths. · **Space:** O(max(N, M)), where N and M are the lengths of the input arrays. This space is used to store the `BigInteger` representations and the final result array.
**Pros:** The approach is conceptually simple, breaking the problem into distinct, understandable steps: convert, add, convert back.; It leverages the powerful and well-tested `BigInteger` class, abstracting away the complexities of large number arithmetic.
**Cons:** Significantly less efficient due to the computational overhead of `BigInteger` arithmetic, especially for multiplication and division operations.; The conversion from decimal back to negabinary requires careful handling of negative remainders, which can be complex and error-prone.
### Explanation
The core idea is to switch from the negabinary system to the familiar decimal system to perform the addition, and then switch back.

**Step 1: Negabinary to Decimal Conversion**
A function is created to convert an array like `[1,1,0,1]` to its decimal value. This is calculated as `1*(-2)^3 + 1*(-2)^2 + 0*(-2)^1 + 1*(-2)^0 = -8 + 4 + 0 + 1 = -3`. We must use `BigInteger` to handle the large numbers that can arise from arrays up to 1000 elements long.
```java
import java.math.BigInteger;

private BigInteger toDecimal(int[] arr) {
    BigInteger result = BigInteger.ZERO;
    BigInteger powerOfNegTwo = BigInteger.ONE;
    BigInteger negTwo = new BigInteger("-2");
    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] == 1) {
            result = result.add(powerOfNegTwo);
        }
        powerOfNegTwo = powerOfNegTwo.multiply(negTwo);
    }
    return result;
}
```

**Step 2: Addition**
The two `BigInteger`s obtained from step 1 are simply added together.
```java
BigInteger num1 = toDecimal(arr1);
BigInteger num2 = toDecimal(arr2);
BigInteger sum = num1.add(num2);
```

**Step 3: Decimal to Negabinary Conversion**
This is the reverse of step 1. We convert the decimal sum back to a negabinary array. The standard algorithm is repeated division by the base (-2) and recording the remainders. However, standard remainders can be negative. We need remainders to be 0 or 1. If a remainder is negative (-1), we adjust it to 1 and add 1 to the quotient to compensate.
```java
private int[] fromDecimal(BigInteger n) {
    if (n.equals(BigInteger.ZERO)) {
        return new int[]{0};
    }
    java.util.List<Integer> list = new java.util.ArrayList<>();
    BigInteger negTwo = new BigInteger("-2");
    while (!n.equals(BigInteger.ZERO)) {
        BigInteger[] divAndRem = n.divideAndRemainder(negTwo);
        BigInteger quotient = divAndRem[0];
        BigInteger remainder = divAndRem[1];
        if (remainder.compareTo(BigInteger.ZERO) < 0) {
            remainder = remainder.add(BigInteger.valueOf(2));
            quotient = quotient.add(BigInteger.ONE);
        }
        list.add(remainder.intValue());
        n = quotient;
    }
    java.util.Collections.reverse(list);
    return list.stream().mapToInt(i -> i).toArray();
}
```
### Algorithm
- 1. Implement a helper function `toDecimal` that takes a negabinary array and converts it to its `java.math.BigInteger` decimal equivalent. This is done by iterating through the array and summing up `arr[i] * (-2)^power`.
- 2. Implement a second helper function `fromDecimal` that converts a `BigInteger` back to a negabinary array. This involves a loop where in each step, the number is divided by -2, and the remainder is taken as the next digit. A special adjustment is needed if the remainder is negative.
- 3. In the main function, use `toDecimal` to convert both input arrays `arr1` and `arr2` into `BigInteger`s.
- 4. Add these two `BigInteger`s using the `add` method.
- 5. Pass the resulting sum to the `fromDecimal` function to get the final negabinary array.
- 6. Return the result.

## Direct Simulation of Negabinary Addition
This approach simulates the process of column-by-column addition directly on the negabinary numbers, much like performing addition by hand. It iterates from the least significant bit (rightmost) to the most significant bit (leftmost), calculating the sum and a carry at each position. The main distinction from standard binary addition is the unique logic for calculating and propagating the carry in a base -2 system.
**Time:** O(max(N, M)), where N and M are the lengths of the input arrays. The algorithm performs a single pass through the digits of the numbers. · **Space:** O(max(N, M)) to store the result. The space used for pointers and the carry is constant.
**Pros:** Highly efficient with an optimal time complexity.; Avoids the overhead and complexity of large number libraries like `BigInteger` by working with small, constant-size integers.; It is a direct and elegant solution that operates within the problem's native negabinary representation.
**Cons:** The carry propagation logic, `carry = -(sum >> 1)`, is non-intuitive compared to standard binary addition and requires a solid understanding of negabinary properties or careful derivation.
### Explanation
This method avoids conversions to other bases and works directly with the negabinary representation. It mimics manual addition.

We iterate from right to left, maintaining a `carry`. The `sum` at each position `k` is `arr1[k] + arr2[k] + carry`. The value at this position must be represented by a digit `d_k` (0 or 1) and a carry to the next position. The relationship is `sum = d_k + (-2) * carry_new`.

From this, we can derive the rules:
- The digit `d_k` is `sum mod 2`. A simple way to compute this is `sum & 1`.
- The new carry is `carry_new = (sum - d_k) / (-2)`. This can be simplified. For any integer `sum`, `(sum - (sum & 1))` is always an even number. Dividing by -2 is equivalent to dividing by 2 and negating. In Java, the bitwise right shift `>>` on `sum` effectively calculates `floor(sum / 2)`. The expression `-(sum >> 1)` correctly computes the new carry for all possible `sum` values (`-1, 0, 1, 2, 3`).

For example:
- If `sum = 2` (1+1+0): `d_k = 2 & 1 = 0`. `carry_new = -(2 >> 1) = -1`.
- If `sum = -1` (0+0-1): `d_k = -1 & 1 = 1`. `carry_new = -(-1 >> 1) = -(-1) = 1`.

The algorithm proceeds until all input digits are processed and the carry becomes zero. Finally, any leading zeros in the result are removed.

```java
import java.util.LinkedList;

public int[] addNegabinary(int[] arr1, int[] arr2) {
    int i = arr1.length - 1;
    int j = arr2.length - 1;
    int carry = 0;
    LinkedList<Integer> result = new LinkedList<>();

    while (i >= 0 || j >= 0 || carry != 0) {
        int bit1 = (i >= 0) ? arr1[i--] : 0;
        int bit2 = (j >= 0) ? arr2[j--] : 0;
        int sum = bit1 + bit2 + carry;
        
        result.addFirst(sum & 1);
        carry = -(sum >> 1);
    }

    // Remove leading zeros
    int firstOneIndex = -1;
    for (int k = 0; k < result.size(); k++) {
        if (result.get(k) == 1) {
            firstOneIndex = k;
            break;
        }
    }

    if (firstOneIndex == -1) { // Result is 0
        return new int[]{0};
    }

    // Convert LinkedList to array, skipping leading zeros
    int[] finalResult = new int[result.size() - firstOneIndex];
    for (int k = 0; k < finalResult.length; k++) {
        finalResult[k] = result.get(firstOneIndex + k);
    }

    return finalResult;
}
```
### Algorithm
- 1. Initialize two pointers, `i` and `j`, to point to the last element of `arr1` and `arr2` respectively.
- 2. Initialize a `carry` variable to `0` and a `LinkedList<Integer>` to store result bits.
- 3. Loop while `i >= 0` or `j >= 0` or `carry != 0`.
- 4. In each iteration, retrieve the current bits from `arr1[i]` and `arr2[j]`. If a pointer is out of bounds, the bit is considered `0`. Decrement the pointers.
- 5. Calculate the `sum` of the two bits and the current `carry`.
- 6. The result bit for the current position is `sum & 1`. Add this bit to the front of the result list.
- 7. Calculate the new carry for the next position (to the left) using the formula `carry = -(sum >> 1)`.
- 8. After the loop, the result list holds the sum in negabinary form, possibly with leading zeros.
- 9. Remove any leading zeros. If the result is all zeros, return `[0]`.
- 10. Convert the final list to an integer array and return it.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] AddNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.Length - 1, j = arr2.Length - 1;
        List < int > ans = new List < int > ();
        for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {
            int a = i < 0 ? 0 : arr1[i];
            int b = j < 0 ? 0 : arr2[j];
            int x = a + b + c;
            c = 0;
            if (x >= 2) {
                x -= 2;
                c -= 1;
            } else if (x == -1) {
                x = 1;
                c = 1;
            }
            ans.Add(x);
        }
        while (ans.Count > 1 && ans[ans.Count - 1] == 0) {
            ans.RemoveAt(ans.Count - 1);
        }
        ans.Reverse();
        return ans.ToArray();
    }
}
```

### Java

```java
class Solution {
public
  int[] addNegabinary(int[] arr1, int[] arr2) {
    int i = arr1.length - 1, j = arr2.length - 1;
    List<Integer> ans = new ArrayList<>();
    for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {
      int a = i < 0 ? 0 : arr1[i];
      int b = j < 0 ? 0 : arr2[j];
      int x = a + b + c;
      c = 0;
      if (x >= 2) {
        x -= 2;
        c -= 1;
      } else if (x == -1) {
        x = 1;
        c += 1;
      }
      ans.add(x);
    }
    while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
      ans.remove(ans.size() - 1);
    }
    Collections.reverse(ans);
    return ans.stream().mapToInt(x->x).toArray();
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> addNegabinary(vector<int> &arr1, vector<int> &arr2) {
    int i = arr1.size() - 1, j = arr2.size() - 1;
    vector<int> ans;
    for (int c = 0; i >= 0 || j >= 0 || c; --i, --j) {
      int a = i < 0 ? 0 : arr1[i];
      int b = j < 0 ? 0 : arr2[j];
      int x = a + b + c;
      c = 0;
      if (x >= 2) {
        x -= 2;
        c -= 1;
      } else if (x == -1) {
        x = 1;
        c += 1;
      }
      ans.push_back(x);
    }
    while (ans.size() > 1 && ans.back() == 0) {
      ans.pop_back();
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]: i, j = len(arr1) - 1, len(arr2) - 1 c = 0 ans = [] while i >= 0 or j >= 0 or c: a = 0 if i < 0 else arr1[i] b = 0 if j < 0 else arr2[j] x = a + b + c c = 0 if x >= 2: x -= 2 c -= 1 elif x == - 1: x = 1 c += 1 ans . append(x) i, j = i - 1, j - 1 while len(ans) > 1 and ans[- 1] == 0: ans . pop() return ans[:: - 1]

```