Problem Description

This problem asks you to add two numbers that are represented in base -2 (negabinary).

In base -2, each position represents a power of -2. For a number represented as an array [1,1,0,1], reading from left to right (most significant to least significant bit), it equals:

• 1 × (-2)³ + 1 × (-2)² + 0 × (-2)¹ + 1 × (-2)⁰
• = 1 × (-8) + 1 × 4 + 0 × (-2) + 1 × 1
• = -8 + 4 + 0 + 1
• = -3

You're given two arrays arr1 and arr2, each representing a number in base -2 format. The arrays contain only 0s and 1s, with the most significant bit at index 0. The arrays are guaranteed to have no leading zeros (except when representing 0 itself, which is [0]).

Your task is to compute the sum of these two numbers and return the result in the same base -2 array format, also without leading zeros.

The solution uses a digit-by-digit addition approach similar to regular binary addition, but with special handling for the base -2 system. The key differences are:

• When the sum at a position is 2 or more, we need to subtract 2 from the current position and subtract 1 from the carry (because the next position represents -2 times the current position's value)
• When the sum is -1, we set the current digit to 1 and add 1 to the carry

The algorithm processes digits from right to left (least significant to most significant), handles the carry appropriately for base -2, and removes any leading zeros from the final result before returning it.

Intuition

The key insight is recognizing that addition in base -2 follows similar principles to regular binary addition, but with a twist in how we handle carries.

In regular binary (base 2), when we add two bits and get a sum ≥ 2, we write down sum % 2 and carry 1 to the next position. This works because each position represents a positive power of 2, so carrying 1 to the next position means adding 2^(i+1), which equals 2 × 2^i.

In base -2, each position alternates between negative and positive powers. Position i represents (-2)^i. When we need to carry from position i to position i+1, we're moving from (-2)^i to (-2)^(i+1) = -2 × (-2)^i.

This creates two special cases:

1. When the sum is 2 or more: We have too many 1s at this position. To fix this, we subtract 2 from the current position (keeping x - 2) and need to account for those 2 units. Since 2 × (-2)^i = -1 × (-2)^(i+1), we carry -1 to the next position.

2. When the sum is -1: We can't have negative digits in our representation. To fix this, we borrow from the next position. Since (-2)^(i+1) = -2 × (-2)^i, borrowing 1 from position i+1 gives us -2 at position i. Adding this to our -1 gives us -3, but we actually want 1 at the current position. So we set the current digit to 1 and carry +1 to compensate.

The algorithm naturally handles these cases by maintaining a carry value that can be positive, negative, or zero, adjusting it based on the sum at each position, and continuing until all digits and carries are processed.

Learn more about Math patterns.

Solution Approach

The implementation uses a two-pointer approach to traverse both arrays from right to left (least significant to most significant bit), similar to traditional addition algorithms.

Algorithm Steps:

1. Initialize pointers and carry: Set i and j to point to the last elements of arr1 and arr2 respectively. Initialize carry c = 0 and an empty result list ans.

2. Main addition loop: Continue while there are digits to process or a carry exists (i >= 0 or j >= 0 or c):

   • Extract current digits: a from arr1[i] (or 0 if out of bounds) and b from arr2[j] (or 0 if out of bounds)
   • Calculate the sum: x = a + b + c
   • Reset carry: c = 0

3. Handle special cases for base -2:

   • If x >= 2: We have overflow at this position
     • Subtract 2 from current digit: x -= 2
     • Set negative carry: c = -1 (because 2 × (-2)^i = -1 × (-2)^(i+1))
   • If x == -1: We have a negative digit which isn't allowed
     • Set current digit to 1: x = 1
     • Set positive carry: c = 1 (to compensate for the adjustment)

4. Store result and move pointers:

   • Append x to ans
   • Decrement both pointers: i -= 1, j -= 1

5. Remove leading zeros: After the loop, remove trailing zeros from ans (which become leading zeros when reversed), keeping at least one element.

6. Return reversed result: Since we built the answer from least to most significant bit, reverse it before returning: ans[::-1]

Data Structure: The solution uses a simple list to build the result, which is efficient for appending elements and allows easy reversal at the end.

Time Complexity: O(max(n, m)) where n and m are the lengths of the input arrays. Space Complexity: O(max(n, m)) for the result array.

Example Walkthrough

Let's add [1,0,1] and [1,1,1] in base -2.

First, let's verify what these numbers represent:

• [1,0,1] = 1×(-2)² + 0×(-2)¹ + 1×(-2)⁰ = 4 + 0 + 1 = 5
• [1,1,1] = 1×(-2)² + 1×(-2)¹ + 1×(-2)⁰ = 4 + (-2) + 1 = 3
• Expected sum: 5 + 3 = 8

Now let's trace through the algorithm:

Initial Setup:

• i = 2, j = 2 (pointing to last elements)
• c = 0 (carry)
• ans = []

Iteration 1 (rightmost position, (-2)⁰):

• a = arr1[2] = 1, b = arr2[2] = 1
• x = a + b + c = 1 + 1 + 0 = 2
• Since x >= 2:
  • x = x - 2 = 0
  • c = -1 (negative carry)
• ans = [0]
• Move pointers: i = 1, j = 1

Iteration 2 (middle position, (-2)¹):

• a = arr1[1] = 0, b = arr2[1] = 1
• x = a + b + c = 0 + 1 + (-1) = 0
• No special case needed
• c = 0
• ans = [0, 0]
• Move pointers: i = 0, j = 0

Iteration 3 (leftmost position, (-2)²):

• a = arr1[0] = 1, b = arr2[0] = 1
• x = a + b + c = 1 + 1 + 0 = 2
• Since x >= 2:
  • x = x - 2 = 0
  • c = -1
• ans = [0, 0, 0]
• Move pointers: i = -1, j = -1

Iteration 4 (new position, (-2)³):

• a = 0 (out of bounds), b = 0 (out of bounds)
• x = 0 + 0 + (-1) = -1
• Since x == -1:
  • x = 1
  • c = 1
• ans = [0, 0, 0, 1]
• Move pointers: i = -2, j = -2

Iteration 5 (new position, (-2)⁴):

• a = 0, b = 0
• x = 0 + 0 + 1 = 1
• No special case needed
• c = 0
• ans = [0, 0, 0, 1, 1]
• Loop ends (no more digits and carry is 0)

Final Steps:

• Remove leading zeros: ans = [0, 0, 0, 1, 1] (no trailing zeros to remove)
• Reverse: ans = [1, 1, 0, 0, 0]

Verification: [1,1,0,0,0] = 1×(-2)⁴ + 1×(-2)³ + 0×(-2)² + 0×(-2)¹ + 0×(-2)⁰ = 16 + (-8) + 0 + 0 + 0 = 8 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(max(n, m)) where n is the length of arr1 and m is the length of arr2.

The algorithm iterates through both arrays from right to left once. The main while loop continues until both indices i and j become negative and there's no carry c. In the worst case, this happens after processing all elements from both arrays plus potentially a few extra iterations for carry propagation. The number of iterations is bounded by max(n, m) + constant, which simplifies to O(max(n, m)).

The second while loop that removes trailing zeros runs at most O(max(n, m)) times since the result array can't be longer than max(n, m) + constant elements.

The final reversal operation ans[::-1] takes O(len(ans)) time, which is also bounded by O(max(n, m)).

Space Complexity: O(max(n, m))

The algorithm uses:

• Variables i, j, c, a, b, x: O(1) space
• The ans list: stores the result digits, which in the worst case can be at most max(n, m) + 1 elements (when there's a carry that extends the result by one position)
• The reversed array returned at the end creates a new list of the same size

Therefore, the total space complexity is O(max(n, m)).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Carry Handling in Base -2

The most common mistake is treating this like regular binary addition where carry is always positive. In base -2, the carry logic is counterintuitive:

Wrong approach:

if current_sum >= 2:
    current_sum -= 2
    carry = 1  # WRONG! Should be -1

Why it's wrong: In base -2, when you have a sum of 2 at position i, it equals 2 × (-2)^i. To carry this to position i+1, you need to recognize that 2 × (-2)^i = -1 × (-2)^(i+1), hence the carry should be -1, not 1.

Correct approach:

if current_sum >= 2:
    current_sum -= 2
    carry = -1  # Correct negative carry

2. Forgetting to Handle Negative Sum

Another pitfall is not handling the case when the sum becomes -1:

Wrong approach:

# Only handling the >= 2 case
if current_sum >= 2:
    current_sum -= 2
    carry = -1
# Missing the -1 case!

Why it's wrong: In base -2, we can only have digits 0 or 1. When the sum is -1 (which can happen with a negative carry), we must convert it to a valid digit.

Correct approach:

if current_sum >= 2:
    current_sum -= 2
    carry = -1
elif current_sum == -1:
    current_sum = 1
    carry = 1

3. Premature Loop Termination

Stopping the loop too early when both arrays are exhausted but carry still exists:

Wrong approach:

while index1 >= 0 or index2 >= 0:  # WRONG! Ignores remaining carry
    # process digits

Why it's wrong: The carry might propagate beyond the length of both input arrays, potentially adding more significant digits to the result.

Correct approach:

while index1 >= 0 or index2 >= 0 or carry != 0:  # Include carry in condition
    # process digits

4. Leading Zeros in Result

Forgetting to remove leading zeros or removing too many:

Wrong approach:

# Forgetting to remove leading zeros entirely
return result[::-1]

# Or removing all zeros (including the case where answer is 0)
while result[-1] == 0:
    result.pop()

Correct approach:

# Keep at least one element to handle the case where the sum is 0
while len(result) > 1 and result[-1] == 0:
    result.pop()
return result[::-1]