python basic math
Intuition\n Describe your first thoughts on how to solve this problem. \nAssumption from basic math\n\n9 = a * (-2) ** x + b * (-2) ** (x-1) + c * (-2) ** (x-2)
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAssumption from basic math\n\n9 = a * (-2) ** x + b * (-2) ** (x-1) + c * (-2) ** (x-2) + ... + 1 \n=> do mod 2 to find last digit => will get 1\n=> new total will be 9 // 2 = 4\n4 = a ** (-2) ** (x-1) + b ** (-2) ** (x-2) + ... + -k => -1 time 2 sides\nfind k by mod2 both side\n-4 = .... + k\n=> repeat the process until total == 0\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\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        n1 = 0\n        power = 0\n        for i in range(len(arr1)-1, -1, -1):\n            n1 += arr1[i] * (-2) ** power\n            power += 1\n\n        n2 = 0\n        power = 0\n        for i in range(len(arr2)-1, -1, -1):\n            n2 += arr2[i] * (-2) ** power\n            power += 1\n\n        total = n1 + n2\n        ans = []\n        while total != 0:\n            rem = abs(total % 2)\n            total = total // 2\n            ans.append(rem)\n            total *= -1\n\n        if not ans:\n            return [0]\n\n        return ans[::-1]\n\n"""\nAssumption from basic math\n\n9 = a * (-2) ** x + b * (-2) ** (x-1) + c * (-2) ** (x-2) + ... + 1 \n=> do mod 2 to find last digit => will get 1\n=> new total will be 9 // 2 = 4\n4 = a ** (-2) ** (x-1) + b ** (-2) ** (x-2) + ... + -k => -1 time 2 sides\nfind k by mod2 both side\n-4 = .... + k\n=> repeat the process until total == 0\n"""\n```
['Python3']