Solution for 1073. Adding Two Negabinary Numbers
Intuition\n Describe your first thoughts on how to solve this problem. \nTo me, Key thing is to understand mechanism of base -2 operation. Note to handle the sp
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo me, Key thing is to understand mechanism of base -2 operation. Note to handle the special cases \n1. -1 carry at the end\n2. handling -1 as sum of digits. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nInitializes variables for processing the vectors and storing the result.\nIterates through both input vectors from the right end simultaneously.\n\nAdds the corresponding elements of the vectors along with the residue multiplied by the multiplier.\n\nCalls the calculate method to update the digit, residue, and multiplier for the current calculation.\n\nInserts the calculated digit at the beginning of the result vector.\n\nHandles scenarios where one input vector is longer than the other by processing the remaining elements.\n\nInserts additional 1\'s at the beginning of the result if there is remaining residue.\n\nTrims any leading zeros from the result.\n\nReturns the final result vector.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(max(arr1.size, arr2.size))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1)\n# Code\n```\nclass Solution {\npublic:\n/*\nRef: Logic mentioned at https://math.stackexchange.com/questions/3251605/how-to-add-negabinary-numbers\nThis method calculates the digit, residue, and multiplier based on the input value.\nIf the input value is -1, sets digit to 1, residue to 1, and multiplier to 1.\nOtherwise, calculates digit as the modulus of the input value divided by 2, residue as the input value divided by 2, and multiplier as -1.\n*/\n    void calculate(int val, int& digit, int& residue, int& multiplier){\n        if(val == -1){\n            digit = 1;\n            residue = 1;\n            multiplier = 1;\n        }else{\n            digit = val % 2;\n            residue = val / 2;\n            multiplier = -1;\n        }\n\n    }\n\n    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {\n        int size1 = arr1.size();\n        int size2 = arr2.size();\n        int i;\n        int j;\n        int residue = 0;\n        int val;\n        vector<int> res;\n        int digit;\n        int multiplier = -1;\n        for(i = size1-1, j=size2-1; i >=0 && j>=0; --i, --j){\n            val = arr1[i] + arr2[j] + residue * multiplier;\n            //multiplier *= -1;\n            calculate(val, digit, residue, multiplier);\n            //cout<<" "<<val<<" "<<digit<<" "<<residue<<endl;\n            res.insert(res.begin(), digit);\n        }\n\n        //cout<<" "<<i<<" "<<j<<endl;\n        while(i >= 0){\n            val = arr1[i] + residue * multiplier;\n            calculate(val, digit, residue, multiplier);\n\n            res.insert(res.begin(), digit);\n            //multiplier *= -1;\n            cout<<" "<<val<<" "<<digit<<" "<<residue<<endl;\n            --i;\n        }\n\n        //cout<<" "<<i<<" "<<j<<endl;\n        while(j >= 0){\n            val = arr2[j] + residue * multiplier;\n            calculate(val, digit, residue, multiplier);\n\n            res.insert(res.begin(), digit);\n            cout<<" "<<val<<" "<<digit<<" "<<residue<<endl;\n            //multiplier *= -1;\n            --j;\n        }\n\n        if(residue){\n            res.insert(res.begin(), 1);\n            res.insert(res.begin(), 1);\n        }\n        //remove leading zeros\n        while(res.size() > 1 && res[0] == 0){\n            res.erase(res.begin());\n        }\n        return res;\n    }\n};\n```
['C++']