Column Addition
Intuition\n Describe your first thoughts on how to solve this problem. \nBased on concept of Column Addition. \n\n# Approach\n Describe your approach to solving
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBased on concept of Column Addition. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFrom right to left, add along the column. If the added value exceeds 1, add to the next columns. \n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n        arr1_len = len(arr1)\n        arr2_len = len(arr2)\n        longest_len = max([arr1_len, arr2_len])\n        # Allocate memory space for answer\n        answer_len = arr1_len + arr2_len + 3\n        answer = [0] * answer_len\n\n        for i in range(longest_len):\n            index = -1 * (i+1)\n            value = answer[index]\n            # Sum the column\n            if (i<arr1_len) and arr1[index]:\n                value += 1\n            if (i<arr2_len) and arr2[index]:\n                value += 1\n            if value in [0,1]:\n                answer[index] = value\n            elif value >= 2:\n                # Add to the next columns\n                if answer[index-1] > 0:\n                    answer[index-1] -= 1\n                    answer[index] = value - 2\n                else:\n                    answer[index-1] = 1\n                    answer[index-2] = 1\n                    answer[index] = value - 2\n        if 1 not in answer:\n            answer = [0]\n        else:\n            answer = answer[answer.index(1):]\n        return answer\n```
['Python3']