#1073

Medium

LeetCode Problem Workspace

Adding Two Negabinary Numbers

Add two numbers represented in negabinary format and return the result in the same format.

Problem Statement

You are given two numbers arr1 and arr2 in base -2. The numbers are represented as arrays where each element is a 0 or 1, starting with the most significant bit. Your task is to return the sum of these numbers, also in base -2, in the same format: an array of 0s and 1s without any leading zeros. Note that the representation may not be in traditional base-2; instead, base -2 alternates between positive and negative powers of 2.

For example, the array arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. Given that arr1 and arr2 have no leading zeros, you are expected to return the result in a similar format with no unnecessary leading bits.

Examples

Example 1

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]

Output: [1,0,0,0,0]

arr1 represents 11, arr2 represents 5, the output represents 16.

Example 2

Input: arr1 = [0], arr2 = [0]

Output: [0]

Example details omitted.

Example 3

Input: arr1 = [0], arr2 = [1]

Output: [1]

Example details omitted.

Constraints

1 <= arr1.length, arr2.length <= 1000
arr1[i] and arr2[i] are 0 or 1
arr1 and arr2 have no leading zeros

Solution Approach

Simulate the Addition

The addition should be performed bit by bit, starting from the least significant digit (rightmost). For each position, compute the sum of corresponding bits from arr1 and arr2, adjusting for carries and negative base effects. Handle the carry by adjusting the current bit and propagating the carry to the next significant digit.

Handle Base -2 Carrying

Since the base is negative, carrying over involves different logic. If the sum at any bit exceeds 1 or is less than 0, we need to adjust the bit and propagate the carry accordingly. Specifically, values of 2 or -1 should be converted to 0 and carry 1, while values of -2 or 1 should be converted to 1 with no carry.

Reversing the Result

After computing the sum, the resulting array might need to be reversed before returning, as the digits were processed starting from the least significant bit. Make sure to adjust for any leading zeros before returning the final result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the length of the input arrays, as we process each bit individually. In the worst case, the complexity will be O(max(len(arr1), len(arr2))) due to the bit-by-bit simulation. The space complexity is O(max(len(arr1), len(arr2))) because we are constructing a new array for the result.

What Interviewers Usually Probe

Candidates should demonstrate an understanding of how base -2 impacts the addition and carry operations.
Candidates should be able to explain how to handle the negative base while adding bits and adjusting the carry.
Look for clarity in how the candidate handles the reversal of the result and removal of leading zeros.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the carry rules for base -2 can lead to incorrect results, especially for large numbers.
Failing to account for negative values when calculating carries, especially when they exceed 1 or fall below 0.
Not removing leading zeros from the final result array, which can result in an incorrect format.

Follow-up variants

Implement the solution without reversing the final array.
Optimize the solution for space complexity by avoiding the creation of unnecessary arrays.
Extend the problem to handle multiple base -2 numbers rather than just two.

FAQ

What is base -2?

Base -2 is a numeral system where the base is negative. Each position in the number represents powers of -2, alternating between positive and negative powers.

How do I handle carries in base -2 addition?

In base -2, carries must be handled by adjusting the current bit and propagating the carry. For sums of 2 or -1, carry 1 to the next position, while sums of -2 or 1 do not require a carry.

What happens if the result has leading zeros?

You must remove any leading zeros from the result array to ensure the output is correctly formatted, following the same pattern as the input.

What is the time complexity of this problem?

The time complexity is O(max(len(arr1), len(arr2))) due to processing each bit individually, with space complexity being O(max(len(arr1), len(arr2))) as well.

Can I extend this problem to multiple negabinary numbers?

Yes, you can extend this problem to handle multiple numbers in base -2 by iteratively adding them, using the same logic for bitwise addition and carry propagation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        i, j = len(arr1) - 1, len(arr2) - 1
        c = 0
        ans = []
        while i >= 0 or j >= 0 or c:
            a = 0 if i < 0 else arr1[i]
            b = 0 if j < 0 else arr2[j]
            x = a + b + c
            c = 0
            if x >= 2:
                x -= 2
                c -= 1
            elif x == -1:
                x = 1
                c += 1
            ans.append(x)
            i, j = i - 1, j - 1
        while len(ans) > 1 and ans[-1] == 0:
            ans.pop()
        return ans[::-1]

Continue Practicing

#1093 statistics from a large sample #1040 moving stones until consecutive ii #1037 valid boomerang