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.
In this approach, we align the input arrays from the least significant bit and implement the addition logic specifically adapted for negabinary numbers. We extend the shorter array with zeros and perform bit addition similar to binary but adjust the carry handling considering the base -2 result.
If the sum at the current position exceeds 1, a negative base affects the carry operation. We iteratively adjust the next two positions as needed to correct the sum, keeping our array free of invalid numbers (>1 or <0).
The provided Python solution reverses both arrays for easy iteration from the least significant bit, balances their lengths with zeros, and then performs addition with adjustment for negabinary carry rules. The result is built by capturing bit sums and managing carry according to negabinary properties, then reversed back before returning.
Time Complexity: O(n), where n is the maximum length of the input arrays.
Space Complexity: O(n), due to the storage required for the output array.
This approach operates by first converting the input negabinary arrays into decimal integers, performing the arithmetic operation in decimal, and then converting the resultant integer back into a negabinary array. This indirect method leverages built-in arithmetic for addition, and custom helper functions are implemented for conversion between bases.
The Python solution defines functions to transform negabinary arrays to decimal numbers and then back again. For each conversion, operations are conducted differently due to the negative base. Thus, decimalToNegabinary adapts its division remainder logic accordingly.
Python
JavaScript
Time Complexity: O(n), primarily due to conversion processes.
Space Complexity: O(n), affected by array storage costs in conversion functions.
| Approach | Complexity |
|---|---|
| Align and Add with Negabinary Logic | Time Complexity: O(n), where n is the maximum length of the input arrays. Space Complexity: O(n), due to the storage required for the output array. |
| Negabinary to Decimal Conversion and Back | Time Complexity: O(n), primarily due to conversion processes. Space Complexity: O(n), affected by array storage costs in conversion functions. |
| Default Approach | — |
| 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 |
6 Adding Two Negabinary Numbers || Weekly Contest 139 || Leetcode • code Explainer • 1,618 views views
Watch 8 more video solutions →Practice Adding Two Negabinary Numbers with our built-in code editor and test cases.
Practice on FleetCode