My python solution (Vertical Addition with Explanation)
Let say we have two number d1 d2 d3 ... dm, and q1 q2 q3... qm (if the two number have different number of digits, we can always left pad the shorter one with a
Let say we have two number d<sub>1</sub> d<sub>2</sub> d<sub>3</sub> ... d<sub>m</sub>, and q<sub>1</sub> q<sub>2</sub> q<sub>3</sub>... q<sub>m</sub> (if the two number have different number of digits, we can always left pad the shorter one with all zeros)\n\nFor k<sup>th</sup> digit d<sub>k</sub> and q<sub>k</sub> there are two scenarios for addition\n\n1. If d<sub>k</sub> + q<sub>k</sub> + carry < 2, then the digit p<sub>k</sub> = d<sub>k</sub> + q<sub>k</sub> + carry, and carry = 0. We move to the next digit position. k = k + 1.\n2. If d<sub>k</sub> + q<sub>k</sub> + carry >= 2, then the digit p<sub>k</sub> = d<sub>k</sub> + q<sub>k</sub> + carry - 2. But we can NOT simply set carry = 1, because position k and position k + 1 has sign difference, since 2*(2<sup>k</sup>) != (-2)<sup>k</sup>. Notice 2*(2<sup>k</sup>) = (-1)*(-2)<sup>k+1</sup> and 2*(2<sup>k</sup>) = (-2)<sup>k+2</sup> + (-2)<sup>k+1</sup>, we can either carry = -1 on k+1<sup>th</sup> position or carry = 1 and carry = 1 for both position k + 1<sup>th</sup> and k + 2<sup>th</sup>. Therefore,\n\t1. If d<sub>k+1</sub> + q<sub>k+1</sub> = 0, the k + 1<sup>th</sup> position is 1 and carry = 1 to position k + 2. We then increase the position k by 2. k = k + 2\n\t2. If d<sub>k +1</sub>+ q<sub>k+1</sub> > 0, then k+1<sup>th</sup> position is d<sub>k+1</sub>+q<sub>k+1</sub> - 1, and carry = 0 to posotion k + 2, because 1<= d<sub>k +1</sub>+ q<sub>k+1</sub> <=2 and 0<= d<sub>k +1</sub>+ q<sub>k+1</sub> - 1 <= 1. We then also increase the position k by 2. k = k + 2.\n\t\nNotice, for the final answer we mush remove all the prevailing zeros. We do the vertical addition by first reverse all the digit and align the two number on the lowest significant digit, so we will remove all the traling zeros. After that, we can reverse the array to get the answer. If the array is empty, we return [0].\n\nAn Example\n```\n        5 4 3 2 1      carry\n\t\t1 1 1 1 1        \n\t\t0 0 1 0 1\n      -------------\n\t\t\t  0 0       0\n\t  -------------\n\t      0 0 0 0       0\n\t  -------------\n\t    1 0 0 0 0       0\n\t  -------------\n\t    1 0 0 0 0\n```\nso, 11111 (11)+ 101(5)=10000(16). That is what we want.\n\nAnother example,\n```\n        5 4 3 2 1      carry\n\t\t1 1 1 0 1        \n\t\t0 0 1 0 1\n      -------------\n\t\t\t  1 0       1\n\t  -------------\n\t      0 1 1 0       0\n\t  -------------\n\t    1 0 1 1 0       0\n\t  -------------\n\t    1 0 1 1 0\n```\nso, 11101(13)+101(5)=10110(18).\n\nBelow is my python implementation\n```python\nclass Solution:\n    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n        arr1 = arr1[::-1]\n        arr2 = arr2[::-1]\n        m = len(arr1)\n        n = len(arr2)\n        if m > n:\n            arr2.extend([0]*(m - n))\n        if m < n:\n            arr1.extend([0]*(n - m))\n        l = len(arr1)\n        arr = []\n        carry = 0\n        i = 0\n        while i < l:\n            d = arr1[i] + arr2[i] + carry\n            if d >= 2:\n                d -= 2\n                arr.append(d)\n                carry = 1\n                if i + 1 < l and arr1[i + 1] + arr2[i + 1] == 0:\n                    arr.append(1)\n                    carry = 1\n                    i += 1\n                elif i + 1 < l and arr1[i + 1] + arr2[i + 1]  != 0:\n                    arr.append(arr1[i + 1] + arr2[i + 1] - 1)\n                    carry = 0\n                    i += 1\n            else:\n                arr.append(d)\n                carry = 0\n            i += 1\n            \n        if carry:\n            arr.append(carry)\n            arr.append(carry)\n        #remove trailing zeros\n        i = len(arr) - 1\n        while i >= 0:\n            if arr[i] == 0:\n                i -= 1\n            else:\n                break\n        if i >= 0:\n            return arr[:i + 1][::-1]\n        else:\n            return [0]\n\t\t\t\n```
[]