Watch 9 video solutions for Adding Two Negabinary Numbers, a medium level problem involving Array, Math. This walkthrough by code Explainer has 1,618 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 zerosProblem Overview: You receive two arrays representing integers written in base -2 (negabinary). Each array stores bits from most significant to least significant. Add the two numbers and return the result as another negabinary array without leading zeros.
This problem looks like normal binary addition but the base is -2 instead of 2. That changes how carry propagation works. When the sum of digits exceeds 1 or becomes negative, the carry must be adjusted using the properties of negative bases.
Approach 1: Align and Add with Negabinary Logic (O(n) time, O(1) space)
Treat the arrays like binary numbers and simulate addition from right to left. Use two pointers starting at the last index of each array and maintain a carry. At each step compute total = a + b + carry. The resulting digit becomes total & 1, but the carry is different from standard binary: carry = -(total >> 1). This works because dividing by -2 flips the sign of the carry. Continue until both arrays and the carry are exhausted, then remove leading zeros from the result. This method runs in O(n) time where n is the longer array length and uses O(1) extra space aside from the output buffer. The solution mainly relies on careful carry management while iterating through the array.
Approach 2: Negabinary to Decimal Conversion and Back (O(n) time, O(1) space with big integers)
Another strategy converts both negabinary arrays into decimal values, adds them, and converts the sum back into base -2. Conversion to decimal multiplies each bit by powers of -2. To convert back, repeatedly divide the number by -2 and adjust the remainder so the digit stays 0 or 1. While conceptually simple, this approach relies on large integer arithmetic and careful remainder handling. In languages without arbitrary precision integers, overflow becomes a concern. The runtime is still O(n) because each digit participates in constant-time operations based on math properties of negative bases.
Recommended for interviews: The direct negabinary addition approach is what interviewers expect. It shows you understand how negative-base arithmetic works and can implement custom carry logic. The conversion approach demonstrates conceptual understanding but may be considered less elegant because it relies on big-number conversion rather than operating directly on the bit arrays.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Align and Add with Negabinary Logic | O(n) | O(1) | Best general solution; direct simulation of negabinary addition without conversions |
| Negabinary to Decimal Conversion and Back | O(n) | O(1) (excluding big integer storage) | Useful for understanding negative base math or when big integer operations are convenient |