💎Python3 | Beats 93% | Detailed Explanation💎
Intuition\nSo in normal binary addition, we have the concept of carrying if we overflow the current slot. However, we need to represent the overflow correctly i
# Intuition\nSo in normal binary addition, we have the concept of carrying if we overflow the current slot. However, we need to represent the overflow correctly in this problem... One key insight: overflow works here is THE OPPOSITE of how it works in normal binary. If we overflow the bit, it means we are actually eliminating the next bit after this one. Think about that for a second. If we add 1 + 1, we get 2. But arithmetically, and in negabinary terms, **the addition operation of these two positive 1\'s are effectively eliminating a -2 from the solution**. It works the other way, too. Say I need to add -2 to -2. The overflow in this bit means we need to eliminate a **positive 4** from our solution. Here we reach the first rule / key observation - **we need to carry a -1 anytime we overflow**. That\'s easy then, we just use that as our carry. But what if we end up in a situation where we have a -1 all by itself? Just an example of 5 + 5- \n- step 1\n    1 0 1 = 5\n    1 0 1 = 5 \n    ? -1 0 = 10\n- step 2 \n ???\n\nTo answer this, we need to reason about what this -1 means and how we can represent it in negabinary. Remember what we said earlier, the -1 means we need to negate this number. And how can we do that? Recall that in normal binary, the number after the current one is always twice the value. So, if we want to get the negative representation of our current number, we need to to **add twice its negative to itself**. And how do we get twice its negative? Well, by carrying a 1! Now let\'s complete the addition of 5+5 per step 2 (broken into steps 2a and 2b for clarity):\n\n- step 2a\n  1 0 1 = 5\n1 0 1 = 5\n(-1) 1 1 0 = 10\n\n- step 2b\n1 0 1 = 5\n1 0 1 = 5\n1 1 1 1 0 = 10 \n\nWe just need to translate this to code now. Our rules are simple, we carry -1 if there\'s an overflow (to negate the next power of -2) and represent any lone -1 as a 1 and a carry of 1 to the next (to get the negative equivalent of X as -2X + X).\n\n# Approach\n\n- Do normal addition on the bit if no overflow, set carry to 0 (if 0+0 - new bit is 0, if 1+0 - new bit is 1, etc.)\n- If overflowed, set carry to -1. Do addition with this carry as usual in the next step.\n- If end up with -1 as current bit, set bit = 1 and carry = 1 to negate value.\n\n# Complexity\nM = len(arr1), N = len(arr2)\n- Time complexity: O(max(M, N))\n\n- Space complexity: O(1)\n\n# Code\n```\nclass Solution:\n    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n        carry = 0\n        M, N = len(arr1), len(arr2)\n        output = []\n        for i in range(max(M, N)):\n            idx1, idx2 = M - 1 - i, N - 1 - i\n            b1, b2 = 0 if idx1 < 0 else arr1[idx1], 0 if idx2 < 0 else arr2[idx2]\n            s = b1 + b2 + carry\n            if s == -1:\n                output.append(1)\n                carry = 1\n            elif s == 0:\n                output.append(0)\n                carry = 0\n            elif s == 1:\n                output.append(1)\n                carry = 0\n            elif s == 2:\n                output.append(0)\n                carry = -1\n            elif s == 3:\n                output.append(1)\n                carry = -1\n        if carry == -1:\n            output.append(1)\n            output.append(1)\n        elif carry == 1:\n            output.append(1)\n    \n        while True:\n            if len(output) == 1:\n                break\n            if output[-1] == 0:\n                output.pop()\n            else:\n                break\n\n        return reversed(output)\n\n\n```
['Python3']