Adjust or Carry method ( C++, with explanation )
Intitution:\nLet\'s just add elements of both numbers in any array to get sum of arr1 and arr2 ( I took result ).\n\nIf an elem of result vector is greater than
# Intitution:\nLet\'s just add elements of both numbers in any array to get sum of arr1 and arr2 ( I took result ).\n\nIf an elem of result vector is greater than 2, it can be balanced in two ways:\n(assuming here that leftmost place is highest bit and rightmost place is lowest bit)\n1. By cancelling values of next place in res if available.\ne.g. If res is [1,2] = ( 1*(-2^1) + 2 * (2^0 ) = 0, can be written as [0,0].\n\n\tThis works because numbers are written on base of -2 so next place value will be in -ve if current value is +ve and vice-versa.\n\n\tconsider another example:\n\tIf result is [0,0,3,4,1,1] it will go as following:\n\t\n\t [0,0,3,4,1,1] -> [0,0,2,2,1,1]\n\t since result[2] = 3 => place value is 3 * (-8) = -24\n\t and result[3] = 4 => place value is 4 * 4 = 16\n\t so if we cancel result[3] by 2 * 4 ( two place values) the result will be \n\t 3 * (-8) + 4 * 4 = 8 = 2 * (-8) + 2 * 4 = 8\n\t \n\t [0,0,2,2,1,1] -> [0,0,1,0,1,1] same as above step.\n\t [0,0,1,0,1,1] will be final answer (ignore or pop two zeros at result[0] and result[1]).\n\n2. By putting a carry if it can not be cancelled with next decimal place value.\ne.g. [0,2] can be written as [1,1,0].\nNote that carry always goes to next two places\nbecause ( as here) 2 = 4 + (-2) + 0 = [1,1,0].\n\n```\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        \n        vector<int> result(1002, 0);\n        \n        for(int i=0; i<arr1.size(); i++) \n            result[i] += arr1[i];\n        for(int i=0; i<arr2.size(); i++) \n            result[i] += arr2[i];\n        \n        for(int i=0; i<result.size(); i++){\n            while(result[i]>=2){\n                result[i] -= 2;\n                if(result[i+1]>0) \n\t\t\t\t\t// balance using next digit.\n                    result[i+1] -= 1; \n                else{\n\t\t\t\t\t// no next digit so post a carry.\n                    result[i+1]++;\n                    result[i+2]++;\n                }\n            }\n        }\n        \n        while(result.size() > 1 && result.back()==0) \n            result.pop_back();\n        reverse(result.begin(), result.end());\n        return result;\n    }\n};\n```\n\n
[]