[Python] iterative
Here I just sum corresponding bits from the input arrays starting from the right and carry the leftover to the next bit using the rule from lookup dictionary. A
Here I just sum corresponding bits from the input arrays starting from the right and carry the leftover to the next bit using the rule from `lookup` dictionary. At the end do not forrget remove leading zeros from the answer.\n\nTime: **O(n)** for iteration\nSpace: **O(1)** if the resulting array is not taken into account\n\nRuntime: 48 ms, faster than **42.11%** of Python online submissions for Adding Two Negabinary Numbers.\nMemory Usage: 13.9 MB, less than **10.53%** of Python online submissions for Adding Two Negabinary Numbers.\n\n```\nclass Solution(object):\n    def addNegabinary(self, arr1, arr2):\n        l1, l2 = len(arr1), len(arr2)\n        i, j = l1 - 1, l2 - 1\n        carry = 0\n        res = deque()\n        \n        lookup = {\n            -1: (1, 1),\n            0: (0, 0),\n            1: (1, 0),\n            2: (0, -1),\n            3: (1, -1),\n        }\n        \n        while i > -1 or j > -1 or carry:\n            cur = (arr1[i] if i > -1 else 0) + (arr2[j] if j > -1 else 0) + carry\n            \n            bit, carry = lookup[cur]\n            res.appendleft(bit)\n            \n            i, j = i - 1, j - 1\n            \n        while len(res) > 1 and res[0] == 0: # remove leading 0s\n            res.popleft()\n            \n        return list(res)\n```
[]