[Python beats 100%]This is my first question I contributed on leetcode, here is my approach
I was asked during an interview and I found that it was quite interesting so I contributed it here.\n\nActually, during the interview, my intuition was to trans
I was asked during an interview and I found that it was quite interesting so I contributed it here.\n\nActually, during the interview, my intuition was to transform the arr1 and arr2 to numbers and add and transform it back to a negabinary number using the way like #1017. \n\nBut later I found out from the [wikipedia](https://en.wikipedia.org/wiki/Negative_base#Addition) that there is a much better way.\n\n```py\nclass Solution(object):\n    def addNegabinary(self, arr1, arr2):\n        """\n        ref:\n            - https://en.wikipedia.org/wiki/Negative_base#Addition\n\n            Carry:          1 \u22121  0 \u22121  1 \u22121  0  0  0\n            First addend:         1  0  1  0  1  0  1\n            Second addend:        1  1  1  0  1  0  0 + addition\n                            --------------------------\n            Number:         1 \u22121  2  0  3 \u22121  2  0  1 when we come with a number, lookup from the hashtable\n            -----------------------------------------\n            Bit (result):   1  1  0  0  1  1  0  0  1\n            Carry:          0  1 \u22121  0 \u22121  1 \u22121  0  0 <- each number will be moved to the carry on the top in the next bit\n        """\n        lookup = {\n            -2: (0, 1), # useless becos \u22122 occurs only during subtraction\n            -1: (1, 1),\n            0: (0, 0),\n            1: (1, 0),\n            2: (0, -1),\n            3: (1, -1),\n        }\n        carry = 0\n        result = []\n        # do addition\n        while len(arr1) > 0 or len(arr2) > 0:\n            a = 0\n            if len(arr1) > 0:\n                a = arr1.pop()\n            b = 0\n            if len(arr2) > 0:\n                b = arr2.pop()\n            temp = a + b + carry\n            res, carry = lookup[temp]\n            result.append(res)\n        # if there is still a carry\n        while carry != 0:\n            res, carry = lookup[carry]\n            result.append(res)\n        # remove leading zeros\n        while len(result) > 1 and result[-1] == 0:\n            result.pop()\n        return result[::-1]\n```\n\nHonestly, I don\'t think I can come up with this. But now I see there are some better approaches, so thank you everyone.\n- [from @lee215](https://leetcode.com/problems/adding-two-negabinary-numbers/discuss/303751/C%2B%2BPython-Convert-from-Base-2-Addition)\n- [from @tiankonguse](https://leetcode.com/problems/adding-two-negabinary-numbers/discuss/303831/ChineseC%2B%2B-1073)\n- [from @litian220](https://leetcode.com/problems/adding-two-negabinary-numbers/discuss/303809/Java-Use-stack-Beat-100)\n- [from @amitnsky](https://leetcode.com/problems/adding-two-negabinary-numbers/discuss/303875/Adjust-or-Carry-method)\n- [from @bupt_wc](https://leetcode.com/problems/convert-to-base-2/discuss/265688/4-line-python-clear-solution-with-explanation)
[]