1833. Negabinary Sum
A lab instrument stores numbers in base -2. A number is an array of 0s and 1s, most significant digit first, and the digit at distance k from the right is multiplied by (-2)^k. The signs alternate from one position to the next, so every integer, positive or negative, has exactly one such form with no leading zeros. The number zero is the single-element array [0].
Given two such numbers a and b, return their sum in the same format, with no leading zeros. Add column by column from the right with a carry, but remember that the carry works differently in base -2 and can be negative. Aim for O(n + m) time, where n and m are the lengths of a and b.
Example 1
- Input:
- a = [1,0,1,1], b = [1,1]
- Output:
- [1,0,1,0]
- Explanation:
The first number is -8 + 0 - 2 + 1 = -9 and the second is -2 + 1 = -1, so the sum is -10, which is 1 1 1 0 in base -2.
Example 2
- Input:
- a = [1,1], b = [1]
- Output:
- [0]
- Explanation:
-1 + 1 = 0, written as the single digit 0.
Example 3
- Input:
- a = [1,0,1], b = [1,0,1]
- Output:
- [1,1,1,1,0]
- Explanation:
Each is 4 + 0 + 1 = 5, so the sum is 10, which is 1 1 1 1 0 in base -2.
Constraints
1 ≤ a.length, b.length ≤ 300
every entry is 0 or 1; no leading zeros except the single array [0]
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)