Fast and Easy O(n) Solution
Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\n\nclass Solution {\npublic:\n    pair<int, int> calculateBitAndCarry(int num) {\n    
# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    pair<int, int> calculateBitAndCarry(int num) {\n        int bit = 0;\n        int carry = 0;\n\n        switch(num) {\n            case 1:\n                bit = 1;\n                carry = 0;\n                break;\n\n            case 2:\n                bit = 0;\n                carry = -1;\n                break;\n\n            case 3:\n                bit = 1;\n                carry = -1;\n                break;\n\n            case 0:\n                bit = 0;\n                carry = 0;\n                break;\n\n            case -1:\n                bit = 1;\n                carry = 1;\n                break;\n\n            default:\n                bit = 0;\n                carry = 0;\n                break;\n        }\n\n        return {bit, carry};\n    }\n\n    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {\n        int n = arr1.size();\n        int m = arr2.size();\n\n        if(n < m) \n            return addNegabinary(arr2, arr1);\n\n        vector<int> vals;\n\n        int carry = 0;\n        for(int i = 0 ; i < m ; i++) {\n            int index1 = n - i - 1;\n            int index2 = m - i - 1;\n\n            int num = arr1[index1] + arr2[index2] + carry;\n\n            pair<int, int> bitAndCarry = calculateBitAndCarry(num);\n\n            int bit = bitAndCarry.first;\n            carry = bitAndCarry.second;\n\n            vals.push_back(bit);\n        }\n\n        for(int i = n - m - 1 ; i >= 0 ; i--) {\n            pair<int, int> bitAndCarry = calculateBitAndCarry(arr1[i] + carry);\n\n            int bit = bitAndCarry.first;\n            carry = bitAndCarry.second;\n\n            vals.push_back(bit);\n        }\n\n        switch(carry) {\n            case 1:\n                vals.push_back(1);\n                break;\n            \n            case 2:\n                vals.push_back(0);\n                vals.push_back(1);\n                break;\n\n            case -1:\n                vals.push_back(1);\n                vals.push_back(1);\n                break;\n\n            default:\n                break;\n        }\n\n        while(vals.size() > 1 && vals.back() == 0)\n            vals.pop_back();\n\n        reverse(vals.begin(), vals.end());\n\n        return vals;\n    }\n};\n```
['Array', 'Math', 'C++']