Just like regular binary addition, except carry can be -1
Intuition
Just like regular binary addition, except carry can be -1 or 1.
Add current two digits, and carry c, the sum can be 0,1,2,3,-1
if 0,2, the resulting d
# Intuition
- Just like regular binary addition, except carry can be -1 or 1. 
- Add current two digits, and carry `c`, the sum can be `0,1,2,3,-1`
- if `0,2`, the resulting digit will be `0`, and `1` if `1, 3`.
- next carry `c` will be `-1` if `2,3`.
- if the sum is `-1`, convert it to `-1 = -2 + 1`, so current sum digit will be `1`, and next `c` will be `1`.

# Approach
- reverse `arr1` and `arr2`, and make them same size by filling `0`s.
- iteratively add digits from left to right
- append `1` if final `c = 1`, and `11` if final `c = -1`.
- reverse result to return.

# Complexity
- Time complexity:
O(N)

- Space complexity:
O(1)

# Code
```cpp []
class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        reverse(arr1.begin(), arr1.end());
        reverse(arr2.begin(), arr2.end());
        int sz = max(arr1.size(), arr2.size());
        arr1.resize(sz);
        arr2.resize(sz);
        int c = 0;
        vector<int> sum;
        for(int i = 0; i < arr1.size() && i < arr2.size(); ++i) {
            int val = arr1[i] + arr2[i] + c;
            if(val == -1) {
                sum.push_back(1);
                c = 1;
            }
            else {
                sum.push_back(val % 2); 
                c = val/2 ? -1 : 0;
            }
        }
        if(c) {
            sum.push_back(1);
            if(c == -1)
                sum.push_back(1);
        }
        while(sum.size() > 1 && !sum.back()) sum.pop_back();
        reverse(sum.begin(), sum.end());
        return sum;
    }
};
```
['C++']