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:
|
|
Example 2:
|
|
Example 3:
|
|
Constraints:
1 <= arr1.length, arr2.length <= 1000
arr1[i]
andarr2[i]
are0
or1
arr1
andarr2
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 acarry
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
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(max(N, M))
, where N and M are the lengths ofarr1
andarr2
. - 🧺 Space complexity:
O(max(N, M))