0ms Runtime - Beats 100% in terms of Runtime
Intuition\nWe observe that 1+1 in this context is not 10 but 110 (4-2+0=2) as the base is -2. So we can do it if we maintain two carries for each bit addition.\
# Intuition\nWe observe that 1+1 in this context is not 10 but 110 (4-2+0=2) as the base is -2. So we can do it if we maintain two carries for each bit addition.\n\n# Approach\nWe start with initialising the two carries c1, c3 to 0. (c2 stores the value of c3 for the next iteration). Then we do bit addition updating the carries accordingly until one of the numbers is finished. So, 2 has c2=1,c1=1, s=0, 3 has c2 = 1, c1=1, s=1, and 4 has c2 = 1, c1=0, s=0.\n\nWe now do this process until the longer number is finished.\nWe finally do it until the carries are over - to avoid getting stuck in an infinite loop, we break in instances like c1 = 1, c2 = 1, c3 = 1 as `((-2)*1+1*(2))*(2^k)=0`.\n\n# Complexity\n- Time complexity:\nO(m+n)\n\n- Space complexity:\nO(m+n)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {\n        reverse(arr1.begin(), arr1.end());\n        reverse(arr2.begin(), arr2.end());\n        int i = 0;\n        int j = 0;\n        int c1 = 0;\n        int c2 = 0;\n        int c3 = 0;\n        vector<int> arr3;\n        while (i<arr1.size() && j<arr2.size()){\n            int s = arr1[i]+arr2[j]+c1+c3;\n            if (s==1 || s==0){\n                arr3.push_back(s);\n                c3 = c2;\n                c1 = 0;\n                c2 = 0;\n            }\n            else if (s==2){\n                arr3.push_back(0);\n                c3 = c2;\n                c1 = 1;\n                c2 = 1;\n            }\n            else if (s==3){\n                arr3.push_back(1);\n                c3 = c2;\n                c1 = 1;\n                c2 = 1;\n            }\n            else{\n                arr3.push_back(0);\n                c3 = c2;\n                c1 = 0;\n                c2 = 1;\n            }\n            j++;\n            i++;\n        }\n        while (i<arr1.size()){\n            int s = arr1[i]+c1+c3;\n            if (s==1 || s==0){\n                arr3.push_back(s);\n                c3 = c2;\n                c1 = 0;\n                c2 = 0;\n            }\n            else if (s==2){\n                arr3.push_back(0);\n                c3 = c2;\n                c1 = 1;\n                c2 = 1;\n            }\n            else if (s==3){\n                arr3.push_back(1);\n                c3 = c2;\n                c1 = 1;\n                c2 = 1;\n            }\n            else{\n                arr3.push_back(0);\n                c3 = c2;\n                c1 = 0;\n                c2 = 1;\n            }\n            i++;\n        }\n        while (j<arr2.size()){\n            int s = arr2[j]+c1+c3;\n            if (s==1 || s==0){\n                arr3.push_back(s);\n                c3 = c2;\n                c1 = 0;\n                c2 = 0;\n            }\n            else if (s==2){\n                arr3.push_back(0);\n                c3 = c2;\n                c1 = 1;\n                c2 = 1;\n            }\n            else if (s==3){\n                arr3.push_back(1);\n                c3 = c2;\n                c1 = 1;\n                c2 = 1;\n            }\n            else{\n                arr3.push_back(0);\n                c3 = c2;\n                c1 = 0;\n                c2 = 1;\n            }\n            j++;\n        }\n        while (c1!=0 || c3!=0){\n            if (c1==1 && c2==1 && c3==1) break;\n            int s = c1+c3;\n            if (s==1 || s==0){\n                arr3.push_back(s);\n                c3 = c2;\n                c1 = 0;\n                c2 = 0;\n            }\n            else if (s==2){\n                arr3.push_back(0);\n                c3 = c2;\n                c1 = 1;\n                c2 = 1;\n            }\n            else if (s==3){\n                arr3.push_back(1);\n                c3 = c2;\n                c1 = 1;\n                c2 = 1;\n            }\n            else{\n                arr3.push_back(0);\n                c3 = c2;\n                c1 = 0;\n                c2 = 1;\n            }\n        }\n        reverse(arr3.begin(),arr3.end());\n        i = 0;\n        while (arr3[i]==0 && i < arr3.size()-1){\n            i++;\n        }\n        vector<int> arr4;\n        arr4 = vector<int> (arr3.begin()+i, arr3.end());\n        return arr4;\n    }\n};\n```
['C++']