## Problem

Problem ID: 1073

Difficulty: Medium

Description:

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 ==  or arr == 1.

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

## Thoughts

I would classify this question as a iykyk kind of question as it hard to encounter for the case for negative number (ie: -1)

## Solution

Intuition:

• If both bit are set at the current bit index, it would borrow from the next bit. Irregardless if the current $$(-2)^{i}$$ is negative

$1*(-2)^i + 1*(-2)^i = -(-2)^{i+1}$
• This is also similar if both the current bit index are set and there is carry from the previous.
• From the previous two points it should be obvious that the carry will minus from the next value instead of borrowing.
• The difficult part is when the bits and the sum adds up to $$-1$$. The following identity could be used.

$-1 = 1*(-2)^0 + 1*(-2)^2$

### Implementation

class Solution {
public:
vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
vector<int> ret;
int arr1_i = arr1.size() - 1;
int arr2_i = arr2.size() - 1;
int carry = 0;

while (arr1_i >= 0 || arr2_i >= 0 || carry != 0) {
int arr1_bit = arr1_i >= 0 ? arr1[arr1_i] : 0;
int arr2_bit = arr2_i >= 0 ? arr2[arr2_i] : 0;
int sum = carry + arr1_bit + arr2_bit;
int ret_bit = sum & 1;
carry = -(sum >> 1);
ret.push_back(ret_bit);
arr1_i--;
arr2_i--;
}

if (carry > 0) ret.push_back(carry);
while (ret.size() > 1 && ret.back() == 0) ret.pop_back();
reverse(ret.begin(), ret.end());
return ret;
}
};