Python 3 | Math, Two Pointers | Explanation
Explanation\n- Math fact for -2 based numbers\n\t- 1 + 1 = 0, carry -1\n\t- -1 + 0 = 1, carry 1 \n\t- 1 + 0 = 1, carry 0\n\t- 0 + 0 = 0, carry 0\n\t- 0 + 1 = 1,
### Explanation\n- Math fact for -2 based numbers\n\t- `1 + 1 = 0, carry -1`\n\t- `-1 + 0 = 1, carry 1` \n\t- `1 + 0 = 1, carry 0`\n\t- `0 + 0 = 0, carry 0`\n\t- `0 + 1 = 1, carry 0`\n\t- `-1 + 1 = 0, carry 0`\n\t- `-1 + -1 is not possible`\n- Based on above fact, we can do a two pointer addition from right to left\n- Remember to count the `carry` and remove the leading `0` before return the answer\n### Implementation\n```\nclass Solution:\n    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n        ans = list()\n        m, n = len(arr1), len(arr2)\n        i, j = m-1, n-1\n        def add(a, b):                                         # A helper function to add -2 based numbers\n            if a == 1 and b == 1:\n                cur, carry = 0, -1\n            elif (a == -1 and b == 0) or (a == 0 and b == -1):    \n                cur = carry = 1\n            else:    \n                cur, carry = a+b, 0\n            return cur, carry                                  # Return current value and carry\n        carry = 0\n        while i >= 0 or j >= 0:                                # Two pointers from right side\n            cur, carry_1, carry_2 = carry, 0, 0\n            if i >= 0:\n                cur, carry_1 = add(cur, arr1[i])\n            if j >= 0:    \n                cur, carry_2 = add(cur, arr2[j])\n            carry = carry_1 + carry_2\n            ans.append(cur)\n            i, j = i-1, j-1\n        ans = [1,1] + ans[::-1] if carry == -1 else ans[::-1]  # Add [1, 1] if there is a carry -1 leftover\n        for i, v in enumerate(ans):                            # Remove leading zero and return\n            if v == 1:\n                return ans[i:]\n        else:\n            return [0]\n```
['Math', 'Two Pointers', 'Python', 'Python3']