Skip to content

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<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
    deque<int> ans;
    int carry = 0;
    int i = arr1.size() - 1;
    int j = arr2.size() - 1;

    while (carry != 0 || 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<Integer> 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 != 0 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]