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.
Example 1:
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:
Input: arr1 = [0], arr2 = [0] Output: [0]
Example 3:
Input: arr1 = [0], arr2 = [1] Output: [1]
Constraints:
1 <= arr1.length, arr2.length <= 1000arr1[i] and arr2[i] are 0 or 1arr1 and arr2 have no leading zerosThe challenge in Adding Two Negabinary Numbers is that the numbers are represented in base -2 instead of the usual positive base. While the addition process still proceeds from the least significant bit to the most significant bit, the carry behavior differs because each position represents powers of -2. When summing bits and a carry, the result may temporarily fall outside the valid binary range of 0 or 1.
A practical approach is to simulate digit-by-digit addition similar to standard binary addition, but normalize the result whenever the sum becomes 2, 3, or negative. This normalization adjusts the current bit and propagates an appropriate carry to the next position based on base -2 arithmetic. Using arrays or stacks to process digits from right to left makes implementation straightforward.
After processing all digits, remove leading zeros while keeping at least one digit if the result is zero. The algorithm runs in linear time relative to the input size.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Simulated Negabinary Addition | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
We can try to determine the last digit of the answer, then divide everything by 2 and repeat.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
While the exact problem may not always appear, concepts like unusual number systems, bit manipulation, and custom carry logic are common in technical interviews at top tech companies.
Arrays or dynamic lists work best because the numbers are already provided as bit arrays. They allow easy traversal from the least significant bit and simple construction of the result.
The optimal approach simulates binary addition while accounting for base -2 carry rules. By processing digits from right to left and normalizing sums to valid bits, you can compute the result efficiently in linear time.
In negabinary representation, each position corresponds to powers of -2 instead of 2. This changes how carries propagate, sometimes producing negative or larger intermediate sums that must be normalized.