# LeetCode: 1073. 负二进制数相加¶

## 1、题目描述¶

输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]



• 1 <= arr1.length <= 1000
• 1 <= arr2.length <= 1000
• arr1 和 arr2 都不含前导零
• arr1[i] 为 0 或 1
• arr2[i] 为 0 或 1

## 2、解题思路¶

• 记住前面的两个进位
• 如果当前位加和为-1，并且下一个进位是1，那么进位清零，如果下一个进位是0，那么产生的当前位为1，进位为1
• 如果当前位加和是0，进位就为0，下一个进位左移，本位为0
• 如果当前位加和是1，进位就为0，下一个进位左移，本位为1
• 如果当前位加和是2，进位就为next_carry - 1，本位为0
• 如果当前位加和是3，进位就为next_carry - 1，本位为1
from itertools import zip_longest

class Solution:
def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
ans = []

carry = [0, 0]

for x, y in zip_longest(reversed(arr1), reversed(arr2), fillvalue=0):
next_carry = carry[1]
cur = carry[0] + x + y
if cur == -1:

if next_carry == 1:
carry = [0, 0]
ans.append(0)
else:
carry = [1, 0]
ans.append(1)

elif cur == 0:
ans.append(0)
carry = [next_carry, 0]
elif cur == 1:
ans.append(1)
carry = [next_carry, 0]
elif cur == 2:
ans.append(0)
carry = [next_carry - 1, 0]
elif cur == 3:
ans.append(1)
carry = [next_carry - 1, 0]

if carry[1]:
ans.extend(carry)
elif carry[0] == -1:
ans.extend([1, 1])

pos = len(ans) - 1
while pos > 0 and ans[pos] == 0:
pos -= 1

return list(reversed(ans[:pos + 1]))