Problem statement

https://leetcode.com/problems/adding-two-negabinary-numbers/

Solution

What we need to do is to use usual schoolbook addition, but know we can have negative carry. Or we can say that we subtract carry instead of adding it. Also in the end we need to remove some leading zeroes.

Complexity

It is O(m + n) for time and O(max(m, n)) for space.

Code

class Solution:
    def addNegabinary(self, a, b):
        i, j, ans, carry = len(a) - 1, len(b) - 1, [], 0
        while i >= 0 or j >= 0 or carry:
            d1 = a[i] if i >= 0 else 0
            d2 = b[j] if j >= 0 else 0
            ans += [(d1 + d2 - carry) % 2]
            carry = (d1 + d2 - carry) // 2
            i, j = i-1, j-1
            
        while len(ans) > 1 and ans[-1] == 0: ans.pop()
        return ans[::-1]