Adding Two Negabinary Numbers

Problem

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array, format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Examples

Example 1:

1
2
3
Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Example 2:

1
2
Input: arr1 = [0], arr2 = [0]
Output: [0]

Example 3:

1
2
Input: arr1 = [0], arr2 = [1]
Output: [1]

Constraints:

1 <= arr1.length, arr2.length <= 1000
arr1[i] and arr2[i] are 0 or 1
arr1 and arr2 have no leading zeros

Solution

Method 1 – Simulation with Carry Handling

Intuition

Negabinary addition is similar to binary addition, but carries behave differently due to the negative base. When the sum at a digit is 2 or -1, we need to adjust the current digit and propagate the carry accordingly. By simulating the addition from least significant to most significant bit, we can construct the result.

Approach

Initialize pointers at the end of both arrays (arr1, arr2) and a carry variable set to 0.
Loop while there are digits left in either array or there is a nonzero carry:

Add the current digits from both arrays (if available) and the carry.
The new digit is sum & 1 (i.e., sum % 2).
Update the carry: carry = -(sum >> 1) (i.e., if sum is 2 or -1, carry becomes -1 or 1).
Append the new digit to the result.

Remove leading zeros from the result, unless the result is [0].
Reverse the result to get the most significant bit first.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
   vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
      int i = arr1.size() - 1, j = arr2.size() - 1, carry = 0;
      vector<int> ans;
      while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += arr1[i--];
        if (j >= 0) sum += arr2[j--];
        ans.push_back(sum & 1);
        carry = -(sum >> 1);
      }
      while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
      reverse(ans.begin(), ans.end());
      return ans;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
   public int[] addNegabinary(int[] arr1, int[] arr2) {
      int i = arr1.length - 1, j = arr2.length - 1, carry = 0;
      List<Integer> ans = new ArrayList<>();
      while (i >= 0 || j >= 0 || carry != 0) {
        int sum = carry;
        if (i >= 0) sum += arr1[i--];
        if (j >= 0) sum += arr2[j--];
        ans.add(sum & 1);
        carry = -(sum >> 1);
      }
      while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) ans.remove(ans.size() - 1);
      int[] res = new int[ans.size()];
      for (int k = 0; k < ans.size(); ++k) res[k] = ans.get(ans.size() - 1 - k);
      return res;
   }
}

 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]:
      i, j, carry = len(arr1) - 1, len(arr2) - 1, 0
      ans: list[int] = []
      while i >= 0 or j >= 0 or carry:
        s = carry
        if i >= 0:
           s += arr1[i]
           i -= 1
        if j >= 0:
           s += arr2[j]
           j -= 1
        ans.append(s & 1)
        carry = -(s >> 1)
      while len(ans) > 1 and ans[-1] == 0:
        ans.pop()
      return ans[::-1]

Complexity

⏰ Time complexity: O(max(N, M)), where N and M are the lengths of arr1 and arr2.
🧺 Space complexity: O(max(N, M))

Problem#

Examples#

Solution#

Method 1 – Simulation with Carry Handling#

Intuition#

Approach#

Code#

Complexity#