Python O(n) space and time solution 2 approaches
First, I tried to solve the problem a simple way:\n\n1. Convert the negabinary numbers to a decimal\n2. Sum the decimal numbers \n3. Convert the decimal number 
First, I tried to solve the problem a simple way:\n\n1. Convert the negabinary numbers to a decimal\n2. Sum the decimal numbers \n3. Convert the decimal number back to a negabinary number\n\n```\nn1 = self.toDecimal(arr1)\nn2 = self.toDecimal(arr2)\nn = n1 + n2\nres = self.toNegabinary(n)\n```\n\n**The most important part is `toNegabinary` function because there is a difference in how we divide a number to 2 and -2, and how we treat negative remainders.**\n\n```\nwhile n != 0:\n    n, remainder = divmod(n, -2)\n    if remainder < 0:\n        n, remainder = n + 1, remainder + 2\n    arr.append(remainder)\n```\n\nLets devide -5 to -2. We should notice that a remainder should be positive; hence, n is 3 not 2, and remider is 1 not -1. We going to use this property in the second approach too. **The problem of this solution is that it only pass 257 cases from 267 cases**. I think it is becasue of the n is big and it returns 0s.\n\nThe second approach is to sum two numbers element by element. The solution is not so different from summing two binary numbers. We should keep in mind the division to -2.\n\n```\ncarry, s = divmod(s, -2)\nif s < 0:\n    carry, s = carry + 1, s + 2\n```\n\nIf we sum 17 and 5 in the decimal system, what do we do? \n1. 7 + 5 = 12, then we 12 % 10 = 2, carry becomes 1\n2. 1 + 0 + carry = 2\n3. so, the sum is 22. \n\nWe do the same here remembering how we shoud do it for -2. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> \n$$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ --> \n$$O(n)$$\n\n# Code\n```\nclass Solution:\n\n    # def toDecimal(self, arr: List[int]) -> int:\n    #     arr.reverse()\n    #     r = 0\n    #     for i, x in enumerate(arr):\n    #         r += math.pow(-2, i) * x\n\n    #     return int(r)\n\n    # def toNegabinary(self, n: int) -> List[int]:\n    #     if n == 0:\n    #         return [0]\n    #     else:\n    #         arr = []\n    #         while n != 0:\n    #             n, remainder = divmod(n, -2)\n    #             if remainder < 0:\n    #                 n, remainder = n + 1, remainder + 2\n    #             arr.append(remainder)\n        \n    #     arr.reverse()\n    #     return arr\n\n    # def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n    #     n1 = self.toDecimal(arr1)\n    #     n2 = self.toDecimal(arr2)\n    #     n = n1 + n2\n    #     res = self.toNegabinary(n)\n    #     return res\n    # it passes 257/267 tests\n\n    def removeZeros(self, arr):\n        while len(arr) > 1 and arr[0] == 0:\n            _ = arr.pop(0)\n        \n        return arr\n\n    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n        carry = 0\n        result = []\n\n        while arr1 or arr2:\n            x = 0 if not arr1 else arr1.pop() \n            y = 0 if not arr2 else arr2.pop()\n\n            s = x + y + carry\n            carry, s = divmod(s, -2)\n            if s < 0:\n                carry, s = carry + 1, s + 2\n            result.append(s)\n        \n        while carry != 0:\n            carry, s = divmod(carry, -2)\n            if s < 0:\n                carry, s = carry + 1, s + 2\n            result.append(s)\n        \n        return self.removeZeros(result[::-1])\n\n\n\n\n        \n```
['Python3']