[Python3] Solved with maths
I wrote down the maths to compute the addition. Here are my findings:\n\nThe main issue is when we add two "ones" at the same position. How do we carry the rema
I wrote down the maths to compute the addition. Here are my findings:\n\nThe main issue is when we add two "ones" at the same position. How do we carry the remainder to the next position? Let us write down the maths. Let us consider our numbers\n\n```\na = sum a_i * (-2)^i\nb = sum b_i * (-2)^i\n```\n\nLet us consider a position `i` such that `a_i` and `b_i` are both equal to 1. In that case:\n\n```\na_i * (-2)^i + b_i * (-2)^i = 2 * (-2)^i = -1 * (-2)^(i + 1)\n```\n\nIn other words, we simply put a `0` at the position `i`, and we carry a `-1` to the next position `i + 1`. The question now is, what happens if `a_(i+1)` and `b_(i+1)` are both zero? We would want to set a `-1` at the position `i + 1`, but that\'s not possible. so we have to rewrite that:\n\n```\n-1 * (-2)^(i + 1) = (-2 + 1) * (-2)^(i + 1) = 1 * (-2)^(i + 1) + 1 * (-2)^(i + 2)\n```\n\nTherefore, if we have a sum of `-1` at a given position, we can simply put a `1` and carry a `+1` to the next position. Finally, this means we can have a sum of `2 + 1 = 3` at a given position; but that\'s easy to solve, as this is similar to the first situation: simply put a `1` rather than a `0` at the current position, and carry a `-1` to the next one.\n\nHere\'s the code implementing that:\n\n```\nclass Solution:\n    \n    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n        carry = 0\n        idx1 = len(arr1) - 1\n        idx2 = len(arr2) - 1\n        ans = []\n        while not (idx1 == -1 and idx2 == -1 and carry == 0):\n            val1 = arr1[idx1] if idx1 >= 0 else 0\n            val2 = arr2[idx2] if idx2 >= 0 else 0\n            val = val1 + val2 + carry\n            if val >= 2:  # case 2 or 3: put 0 or 1, and carry -1 to next position.\n                ans.append(val % 2)\n                carry = -1\n            elif val == -1:  # case -1: put a 1, and carry +1 to next position.\n                ans.append(1)\n                carry = 1\n            else:  # case 0 or 1: no carry in that case.\n                ans.append(val)\n                carry = 0\n            idx1 = max(-1, idx1 - 1)\n            idx2 = max(-1, idx2 - 1)\n        while len(ans) >= 2 and ans[-1] == 0:  # remove trailing zeros.\n            ans.pop()\n        return ans[::-1]\n```
[]