Adding Two Negabinary Numbers: Base -2 Arithmetic

Given two numbers arr1 and arr2 in base -2, return the result of adding them. Each array represents a number where the most significant bit is at index 0, and each element is 0 or 1. The result should also be an array of 0s and 1s with no leading zeros (except for the number zero itself, which is [0]). This is LeetCode 1073: Adding Two Negabinary Numbers.

Negabinary (base -2) is one of those topics that sounds exotic but turns out to be a clean exercise in carry propagation. If you can add two binary numbers, you already have most of the intuition you need. The twist is that the carry behaves differently because the base is negative, and that single difference is exactly what makes this problem worth studying.

Why this problem matters

Base -2 representation is a real concept from computer science theory. Unlike standard binary (base 2), negabinary can represent both positive and negative integers without a sign bit. The position values alternate between positive and negative: 1, -2, 4, -8, 16, -32, .... This means every integer has a unique representation, and you never need a minus sign.

The problem tests whether you can generalize the familiar concept of carry-based addition to an unfamiliar number system. In a standard binary addition, when the sum at a position is 2 or more, you carry 1 to the next position. In base -2, a sum of 2 means you need to carry -1 to the next position, because 2 = 0 + (-1) * (-2). And a sum of -1 means you need to carry 1, because -1 = 1 + 1 * (-2). Those two carry rules are the entire core of the problem.

Once you internalize the carry logic, the rest of the code looks almost identical to the "Add Binary" problem. That makes this a great exercise in pattern transfer: taking a known algorithm and adapting it to a new domain.

The key insight

Addition in any base follows the same structure: process digits from right to left, compute a sum (digit + digit + carry), extract the current digit and the new carry, and move on. The only thing that changes between bases is how you compute the digit and carry from the sum.

In base -2, the rules are:

• If sum is 0 or 1, the digit is sum and the carry is 0. Same as binary.
• If sum is 2, the digit is 0 and the carry is -1. This is because 2 = 0 + (-1) * (-2).
• If sum is -1, the digit is 1 and the carry is 1. This is because -1 = 1 + 1 * (-2).
• If sum is 3, the digit is 1 and the carry is -1. This is because 3 = 1 + (-1) * (-2).

You can derive all of these from a single formula: digit = sum & 1 and carry = -(sum >> 1). The bitwise AND with 1 gives you the least significant bit (the digit), and negating the arithmetic right shift by 1 gives you the correct carry for base -2. This formula works because shifting right in base -2 is equivalent to dividing by -2, but since we are working with the sum of bits (which is a small integer between -1 and 3), we can use the standard bitwise trick and just negate.

The solution

def add_negabinary(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 != 0:
        total = carry
        if i >= 0:
            total += arr1[i]
            i -= 1
        if j >= 0:
            total += arr2[j]
            j -= 1

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

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

    return result[::-1]

The function uses two pointers, i and j, starting from the rightmost elements of both arrays. This mirrors how you would add numbers by hand, processing from the least significant bit upward.

In each iteration, we compute the total as the sum of the current digits from both arrays (if they still have digits left) plus the carry. The digit for the current position is total & 1, which extracts the last bit. The new carry is -(total >> 1), which is the negabinary carry formula.

We append each digit to a result list that builds the answer from least significant to most significant bit. After the loop ends, we strip any trailing zeros (which are leading zeros in the final answer) and reverse the list to get the correct order.

The while loop condition carry != 0 is important. Unlike binary addition where the carry is always 0 or 1, negabinary carry can be -1. A carry of -1 at the end means there are still digits to produce, which could generate further carries. The loop naturally handles this until the carry settles to 0.

Visual walkthrough

Let's trace through adding arr1 = [1,1,1,1,1] (decimal 11) and arr2 = [1,0,1] (decimal 5). Watch how the carry alternates between 0 and -1 as we process each position from right to left.

The carry of -1 appears whenever the sum at a position is 2. It propagates to the next position and gets absorbed when it cancels with a 1. By the time we finish all positions, the carry is 0 and no extra digits are needed. The final result [1,0,0,0,0] represents 1*16 + 0*(-8) + 0*4 + 0*(-2) + 0*1 = 16, confirming that 11 + 5 = 16.

Complexity analysis

Time is O(max(n, m)) where n and m are the lengths of the two input arrays. We process each position exactly once, and the carry loop adds at most a constant number of extra iterations (the carry always resolves within a couple of extra steps).

Space is O(max(n, m)) for the result array, which can be at most a few digits longer than the longer input. In the worst case, the result has max(n, m) + 2 digits.

The building blocks

1. Carry propagation in a non-standard base

The core pattern is computing digit and carry from a sum in base -2:

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

This two-line formula replaces what would otherwise be a chain of conditionals. The same structural pattern appears in any problem that involves digit-by-digit arithmetic: Add Binary, Add Two Numbers, Multiply Strings. The only difference across these problems is the base and how carry is computed. Once you recognize that the skeleton (right-to-left loop with carry) stays fixed and only the carry rule changes, you can adapt to any base.

2. Two-pointer right-to-left traversal

The pattern of using two pointers starting from the end of two arrays and moving left:

i, j = len(arr1) - 1, len(arr2) - 1
while i >= 0 or j >= 0 or carry != 0:
    total = carry
    if i >= 0:
        total += arr1[i]
        i -= 1
    if j >= 0:
        total += arr2[j]
        j -= 1

This avoids the need to pad the shorter array with leading zeros. Each pointer independently checks whether it still has digits to contribute. You will see this exact structure in Add Binary, Add Two Numbers II, and any problem that adds two sequences of different lengths from right to left.

Edge cases

• Both arrays are [0]: the sum is 0 and the result should be [0], not an empty array. The trailing-zero stripping must preserve at least one element.
• Result has leading zeros: when the addition produces leading zeros (for example, [1,0] + [1,0] in base -2), you need to strip them. The while len(result) > 1 and result[-1] == 0 loop handles this.
• Carry extends beyond both arrays: for inputs like [1] + [1], the sum at position 0 is 2, producing carry -1. That carry produces digit 1 at position 1 with carry 1. That carry then produces digit 1 at position 2 with carry 0. Result: [1,1,0].
• One array is much longer than the other: the two-pointer approach naturally handles asymmetric lengths without padding.

From understanding to recall

The logic of negabinary addition fits in a few lines of code, but the details are slippery. Which direction does the carry go, is it -1 or 1, do you negate the shift or not? These details are easy to mix up under pressure, and looking them up during an interview is not an option.

Spaced repetition closes that gap. You practice writing the carry formula, the two-pointer traversal, and the leading-zero cleanup from memory at increasing intervals. After a few rounds, the -(total >> 1) trick is automatic. You see "add two numbers in base -2" and the code flows out without hesitation. That is the difference between understanding a problem and being able to solve it under a timer.

Related posts

• Add Binary - Standard binary addition, the foundation for understanding base -2
• Add Two Numbers - Linked list addition with carry propagation
• Multiply Strings - Digit-by-digit arithmetic on large numbers

CodeBricks breaks Adding Two Negabinary Numbers into its carry-propagation and two-pointer building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an unusual arithmetic problem shows up in your interview, you do not fumble with the carry logic. You just write it.