# 1073. Adding Two Negabinary Numbers

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: vector addNegabinary(vector& arr1, vector& arr2) { deque ans; int carry = 0; int i = arr1.size() - 1; int j = arr2.size() - 1; while (carry || i >= 0 || j >= 0) { if (i >= 0) carry += arr1[i--]; if (j >= 0) carry += arr2[j--]; ans.push_front(carry & 1); carry = -(carry >> 1); } while (ans.size() > 1 && ans.front() == 0) ans.pop_front(); return {ans.begin(), ans.end()}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int[] addNegabinary(int[] arr1, int[] arr2) { Deque ans = new ArrayDeque<>(); int carry = 0; int i = arr1.length - 1; int j = arr2.length - 1; while (carry != 0 || i >= 0 || j >= 0) { if (i >= 0) carry += arr1[i--]; if (j >= 0) carry += arr2[j--]; ans.addFirst(carry & 1); carry = -(carry >> 1); } while (ans.size() > 1 && ans.getFirst() == 0) ans.pollFirst(); return ans.stream().mapToInt(Integer::intValue).toArray(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]: ans = [] carry = 0 while carry or arr1 or arr2: if arr1: carry += arr1.pop() if arr2: carry += arr2.pop() ans.append(carry & 1) carry = -(carry >> 1) while len(ans) > 1 and ans[-1] == 0: ans.pop() return ans[::-1]