My solution
IntuitionWe simply add the numbers in the same pattern as binary, but now, instead of multiplying by 1, we multiply by -2.
To add two negabinary numbers, you ca
# Intuition
We simply add the numbers in the same pattern as binary, but now, instead of multiplying by 1, we multiply by -2.
To add two negabinary numbers, you can use the following formula: at each digit position (from least significant bit/rightmost bit), sum the corresponding bits from both numbers along with the carry from the previous position, then **modulo 2 to get the current digit**; if the sum is greater than 1, set the carry to -1 and set current digit of result to be 0, otherwise set the carry to 0 and current digit of result to be sum; repeat this process until all digits are processed, remembering to adjust the final result based on the remaining carry.

# Approach
First, I create an empty list, and an integer n as 2 plus length of the larger array.
Then, I reverse 2 arrays.
Next, I create a pointer i at the beginning and carry as 0.
Then, I loop until i equals n. During the loop, I create the first bit as i-th element of first array, and 2nd bit as ith element of 2nd array, as long as i is smaller than the length of each. If i is at least equal to length of 1st array, I set first bit to be 0. The same for 2nd bit. Then I add 2 bits together with the carry, and create an integer r as sum modulo by 2. Then, I divide carry by -2. If r is negative, I add 2 to r (make sure it's just between 0 and 1), and increase carry by 1. Then, I add r to res. Finally, I increase i by 1 to go to the next position.
Whereupon, I remove all trailing 0s from the list, reverse it, and finally return it.

# Complexity
- Time complexity:
O(n*n)

- Space complexity:
O(n)

# Code
```cpp []
class Solution {
private:

public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        
        vector<int>res;
        int n=max(arr1.size(),arr2.size())+2;
        reverse(arr1.begin(),arr1.end());
        reverse(arr2.begin(),arr2.end());
        int i=0,carry=0;
        while(i<n){
            int bit_1=(i<arr1.size())?arr1[i]:0;
            int bit_2=(i<arr2.size())?arr2[i]:0;
            int sum=bit_1+bit_2+carry;
            int r=sum%2;
            carry=sum/(-2);
            if(r<0){
                r+=2;
                carry++;
            }
            res.push_back(r);
            i++;
        }
        while(res.size()>1 && res.back()==0){
            res.pop_back();
        }
        reverse(res.begin(),res.end());
        return res;

    }
};
```
['Array', 'Math', 'C++']