Beats 99% Cases Python
Intuition\nWe can break down the numbers mathematically and see what happens to each digit at each stage. For example, adding [1] and [1] is performing \n\n$(-2
# Intuition\nWe can break down the numbers mathematically and see what happens to each digit at each stage. For example, adding [1] and [1] is performing \n\n$(-2)^0 + (-2)^0  = (2)(-2)^0 = (-2)^1 + (4-2)(-2)^0 = (-2)^2 + (-2)^1$\n\nwhich encoded in negabinary as [1, 1, 0].\n\nWe apply this arithmetic knowledge to all cases at each digit $$n $$, and can prove that we only ever need to hold on to two "carry-ons": one for digit $$n+1$$ and one for digit $$n+2$$\n# Approach\n**Cases:**\n    **0.** $$0 * (-2)^n + 0 * (-2)^n = 0 * (-2)^n$$\n    **1.** $$1 * (-2)^n + 0 * (-2)^n = 1 * (-2)^n = (-2)^n$$\n    **2.** $$1 * (-2)^n + 1 * (-2)^n = 2 * (-2)^n = (4-2) * (-2)^n = (-2)^{n+2} + (-2)^{n+1}$$\n\n*You can have a maximum of num 1 + num 1 + carry-on 1 + carry-on 1 so 4, which is two more cases*\n    **3.** $$1 * (-2)^n + 1 * (-2)^n + 1 * (-2)^n = (4-2+1) * (-2)^n = (-2)^{n+2} + (-2)^{n+1} + (-2)^n$$\n    **4.** $$1 * (-2)^n + 1 * (-2)^n + 1 * (-2)^n + 1 * (-2)^n = (4) * (-2)^n = (-2)^{n+2}$$\n    These are all the cases since you can at most impose a carry on two digits forward\n\n**Summarizing the conditions, we have, if the digit sum is:**\n    **0.** Make this digit as 0\n    **1.** Make this digit as 1\n    **2.** Make this digit 0, carry_on 1 += 1, carry_on 2 is 1\n    **3.** Make this digit 1, carry_on 1 += 1, carry_on 2 is 1\n    **4.** Make this digit 0, carry_on 2 is 1\n\n\n**Special Condition**: If ever carry_on_two is 1, carry_on is 2, they need to cancel out, so add that as a check or else we risk infinite loop\n\nLastly, at the end we pop off any leading zeroes just in case\n\n# Complexity\n- Time complexity:\nO(n) $\\rightarrow$ we just traverse both arrays once\n\n- Space complexity:\nO(n) $\\rightarrow$ we build the new number, keep track of some carry_on values too but that\'s it\n\n# Code\n```python3 []\n\nfrom collections import deque\nclass Solution:\n    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n        arr1_index = len(arr1) - 1\n        arr2_index = len(arr2) - 1\n        carry_on = 0\n        carry_on_two = 0\n        final = deque([])\n        while arr1_index >= 0 or arr2_index >= 0 or carry_on > 0 or carry_on_two > 0:\n            print(arr1_index, arr2_index)\n            digit_sum = carry_on\n            if arr1_index >= 0:\n                digit_sum += arr1[arr1_index]\n                arr1_index -= 1\n            if arr2_index >= 0:\n                digit_sum += arr2[arr2_index]\n                arr2_index -= 1\n            carry_on = carry_on_two\n            carry_on_two = 0\n            if digit_sum == 0:\n                digit_value = 0\n            elif digit_sum == 1:\n                digit_value = 1\n            elif digit_sum == 2:\n                digit_value = 0\n                carry_on += 1\n                carry_on_two += 1\n            elif digit_sum == 3:\n                digit_value = 1\n                carry_on += 1\n                carry_on_two += 1\n            elif digit_sum == 4:\n                digit_value = 0\n                carry_on_two += 1\n\n            if carry_on == 2 and carry_on_two == 1:\n                carry_on = 0\n                carry_on_two = 0\n\n            final.appendleft(digit_value)\n        while (len(final) > 1 and final[0] == 0):\n            final.popleft()\n        return list(final)\n\n        \n```
['Python3']