C++ Solution O(N)
Runtime: 4 ms, faster than 96.48% of C++ online submissions for Adding Two Negabinary Numbers.\nMemory Usage: 19.4 MB, less than 87.32% of C++ online submission
Runtime: 4 ms, faster than 96.48% of C++ online submissions for Adding Two Negabinary Numbers.\nMemory Usage: 19.4 MB, less than 87.32% of C++ online submissions for Adding Two Negabinary Numbers.\n\n\n```\nWe can add 2 negabinary number same way we add 2 binary number.\n\nIn case of Base 2 binary number addition we get the Bit and Carry from Sum \n\nSum = Carry + 1st number Bit + 2nd number Bit\n\nNow the current Bit and Carry comes from the binary representation of the Base 2 Sum \n\nValue => Carry | Bit (Binary Representation in Base 2)\n0 => 0 | 0\n1 => 0 | 1\n2 => 1 | 0\n3 => 1 | 1\n\nSame way in case of Base -2 binary number addition we get Bit and Carry from the binary representation of Sum\n\nValue =>  Carry | Bit (Binary Representation in Base -2) \n-2 => 1 | 0\n-1 => 1 | 1\n0 => 0 | 0\n1 => 0 | 1\n2 => 1 1 | 0 => Carry 11 is actually binary representation of -1\n3 => 1 1 | 1 => Carry 11 is actually binary representation of -1\n\nSo we prestore these Bit and Carry in array for -2 to 3 Sum values in vector and perform binary addition.\n```\n\n```\nclass Solution {\npublic:\n    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {\n        \n        int i = arr1.size()-1;\n        int j = arr2.size()-1;\n\n        // prestore bits and carry for different sum values\n        vector<int>bits = {0,1,0,1,0,1};\n        vector<int>carries = {1,1,0,0,-1,-1};\n        \n        vector<int>res;\n        \n        int sum;\n        int carry = 0;\n        \n        // perform binary addition using sum and prestored bit and carry values\n        while(i>=0 || j>=0 || carry)\n        {\n            sum = carry + (i>=0 ? arr1[i--] : 0) + (j>=0 ? arr2[j--] : 0);\n            \n            carry = carries[sum+2];\n\n            res.push_back(bits[sum+2]);\n        }\n        \n        // remove leading zeroes\n        while(res.size() > 1 && res.back()==0)res.pop_back();\n        \n        reverse(res.begin(),res.end());\n        \n        return res;\n    }\n};\n```\n\n\n\n\n
['Math', 'C']