Python. Time: O(n), Space: O(1)
Approach\n Describe your approach to solving the problem. \nFor any index/bit in two arrays, following scenarios apply:\n1. Sum of their coefficients [0,1], the
# Approach\n<!-- Describe your approach to solving the problem. -->\nFor any index/bit in two arrays, following scenarios apply:\n1. Sum of their coefficients [0,1], then leave it as is in result.\n2. Sum of their coefficients is > 1. In this situation, next higher bit can have coefficient contribution of -(current coefficient sum)//2.\n3. Sum of their coefficients is < 0. In this situation, next higher bit can have coefficient contribution of +(current coefficient sum)//2. \n\n# Complexity\n- Time complexity: $$O(n)$$ - Three traversals at worst - One traversal to calculate bit coefficients, second to remove leading zeros, and third for reversing the list.\n\n- Space complexity: $$O(1)$$ - Bit coefficients are calculated and stored in the result array which is returned.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python []\nclass Solution(object):\n    def addNegabinary(self, arr1, arr2):\n        """\n        :type arr1: List[int]\n        :type arr2: List[int]\n        :rtype: List[int]\n        """\n        \n        l1 = len(arr1)\n        l2 = len(arr2)\n\n        res = [0]\n        i3 = 0\n\n        i1 = l1-1\n        i2 = l2-1\n\n        while i1 >= 0 or i2 >= 0:\n            if i3 >= len(res):\n                res.append(0)\n            \n            cur = res[i3]\n            if i1 >= 0:\n                cur += arr1[i1]\n                i1 -= 1\n            if i2 >= 0:\n                cur += arr2[i2]\n                i2 -= 1\n            \n            if cur > 1:\n                carry = cur//2\n                if cur & 1:\n                    res[i3] = 1\n                else:\n                    res[i3] = 0\n                \n                if i3 + 1 >= len(res):\n                    res.append(0)\n                res[i3+1] -= carry\n            elif 0 <= cur <= 1:\n                res[i3] = cur\n            else:\n                if (-cur) & 1 == 0:\n                    res[i3] = 0\n                    if i3 + 1 >= len(res):\n                        res.append(0)\n                    res.append((-cur)//2)\n                else:\n                    res[i3] = 1\n                    if i3 + 1 >= len(res):\n                        res.append(0)\n                    \n                    carry = (-cur+1)//2\n                    res[i3+1] += carry\n            \n            i3 += 1\n        \n        while res[-1] != 0 and res[-1] != 1:\n            if res[-1] > 1:\n                cur = res[-1]\n                if cur & 1:\n                    res[-1] = 1\n                else:\n                    res[-1] = 0\n                \n                res.append(-(cur//2))\n            else:\n                cur = -res[-1]\n\n                if cur & 1:\n                    res[-1] = 1\n                    res.append((cur+1)//2)\n                else:\n                    res[-1] = 0\n                    res.append(cur//2)\n            \n\n        while len(res) > 1:\n            if res[-1] == 0:\n                res.pop(-1)\n            else:\n                break\n        \n        #print res\n        res.reverse()\n        return res\n\n            \n            \n```
['Python']