LeetCode 1073: Adding Negative Numbers

Problem Restatement

We are given two arrays arr1 and arr2 representing two non-positive integers in base 10.

Each array has -1 as the first element (sign) followed by the digits.

We need to return the sum of the two numbers, also in the same format.

The official constraints are similar to LeetCode 66 (Plus One) but for non-positive integers.

Input and Output

Function shape:

def addNegabinary(arr1: list[int], arr2: list[int]) -> list[int]:
    ...

Note

This is actually LeetCode 1073: Adding Negative Numbers which asks to add two numbers in negabinary (base -2) representation.

Problem Restatement (Corrected)

We are given two non-empty arrays arr1 and arr2 representing two numbers in base -2 (negabinary).

Each array has digits in most-significant-first order.

Return the sum in negabinary representation (no leading zeros except [0]).

Examples

Example 1:

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

arr1 = 11111 in base -2 = 11.

arr2 = 101 in base -2 = 5.

Sum = 16 = 10000 in base -2 = [1, 0, 0, 0, 0].

Answer:

[1, 0, 0, 0, 0]

Key Insight

Add digit by digit from least significant to most significant, maintaining a carry. The carry in negabinary can be 0 or -1 (since carrying from position k removes (-2)^k and adds (-2)^(k+1)/(-2)).

When digit_sum = digit1 + digit2 + carry:

• The current output bit is digit_sum & 1, which is always 0 or 1.
• The carry for the next position is -(digit_sum // 2).

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def addNegabinary(self, arr1: list[int], arr2: list[int]) -> list[int]:
        i, j = len(arr1) - 1, len(arr2) - 1
        carry = 0
        result = []

        while i >= 0 or j >= 0 or carry:
            val = carry
            if i >= 0:
                val += arr1[i]
                i -= 1
            if j >= 0:
                val += arr2[j]
                j -= 1

            result.append(val & 1)
            carry = -(val >> 1)

        while len(result) > 1 and result[-1] == 0:
            result.pop()

        return result[::-1]

Testing

def run_tests():
    s = Solution()

    assert s.addNegabinary([1,1,1,1,1], [1,0,1]) == [1,0,0,0,0]
    assert s.addNegabinary([0], [0]) == [0]
    assert s.addNegabinary([0], [1]) == [1]

    print("all tests passed")

run_tests()