LeetCode 1073 - Adding Two Negabinary Numbers

The problem asks us to add two numbers that are represented in negabinary, which is base -2. Unlike standard binary (base 2), each bit in negabinary contributes a value multiplied by powers of -2.

leetcodemediumarraymath

LeetCode Problem 1073

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to add two numbers that are represented in negabinary, which is base -2. Unlike standard binary (base 2), each bit in negabinary contributes a value multiplied by powers of -2. For example, the array [1,1,0,1] represents:

1 * (-2)^3 + 1 * (-2)^2 + 0 * (-2)^1 + 1 * (-2)^0
= -8 + 4 + 0 + 1
= -3

The input consists of two arrays arr1 and arr2, each containing only 0 or 1 values, representing numbers without leading zeros (except for [0]). The output must also be in the same negabinary array format without leading zeros.

The constraints indicate that arrays can be up to length 1000, so any approach that converts the arrays to a standard integer type and then adds may fail due to potential overflow, especially in languages with fixed-width integers. We must therefore design a solution that handles the arithmetic directly in negabinary form.

Edge cases to consider include adding [0] with [0], adding [0] with a non-zero number, and arrays of different lengths. Negabinary addition rules differ from standard binary, especially because carries can be negative and propagate differently.

Approaches

Brute Force

A naive approach is to convert both negabinary arrays to decimal integers, perform standard addition, and then convert the result back to negabinary. This works correctly because the mathematical definition of negabinary allows conversion to decimal and back. However, with arrays of length 1000, the decimal value can become extremely large, potentially exceeding standard integer limits and incurring significant computational overhead.

Optimal Approach

The optimal approach performs direct negabinary addition without converting to decimal. The key observation is that in base -2, the carry rules differ from standard binary. We add corresponding bits from the least significant end and manage carries using the formula:

total = bit1 + bit2 + carry
new_bit = total & 1        # bit value is modulo 2
carry = -(total >> 1)      # carry is negative half of total

This method handles both positive and negative carries automatically. By processing from the least significant bit to the most, we build the result efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n + m) conversion + O(log N) addition O(n + m) Convert to decimal, add, convert back; may overflow
Optimal O(max(n, m)) O(max(n, m)) Direct negabinary addition using carry propagation

Algorithm Walkthrough

  1. Reverse both input arrays so we can process from least significant bit to most.
  2. Initialize a result list and set carry = 0.
  3. Iterate through indices up to the maximum length of the two arrays.
  4. For each index, sum the corresponding bits from both arrays plus the carry.
  5. Compute the new bit as total % 2 and append to the result.
  6. Update the carry as -(total // 2). This handles negative carries correctly due to the base -2.
  7. After finishing all bits, continue processing if carry is not zero, following the same rules.
  8. Reverse the result list to restore the most significant bit first.
  9. Remove any leading zeros unless the result is [0].

Why it works: This algorithm maintains the invariant that at each step, the sum of the processed bits plus the carry represents the correct total in negabinary. The special carry formula ensures that negative contributions propagate correctly, yielding a correct final result.

Python Solution

from typing import List

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 != 0:
            total = carry
            if i >= 0:
                total += arr1[i]
                i -= 1
            if j >= 0:
                total += arr2[j]
                j -= 1
            
            # Compute new bit and carry
            result.append(total & 1)
            carry = -(total >> 1)
        
        # Remove leading zeros
        while len(result) > 1 and result[-1] == 0:
            result.pop()
        
        return result[::-1]

Implementation Explanation: We iterate from the least significant bit to the most significant, summing the corresponding bits and the carry. The bitwise operations &1 and >>1 efficiently compute the new bit and carry. Leading zeros are removed after the calculation, and we reverse the result for correct MSB-to-LSB ordering.

Go Solution

func addNegabinary(arr1 []int, arr2 []int) []int {
    i, j := len(arr1)-1, len(arr2)-1
    carry := 0
    result := []int{}
    
    for i >= 0 || j >= 0 || carry != 0 {
        total := carry
        if i >= 0 {
            total += arr1[i]
            i--
        }
        if j >= 0 {
            total += arr2[j]
            j--
        }
        
        result = append(result, total & 1)
        carry = -(total >> 1)
    }
    
    // Remove leading zeros
    for len(result) > 1 && result[len(result)-1] == 0 {
        result = result[:len(result)-1]
    }
    
    // Reverse the result
    for k, n := 0, len(result); k < n/2; k++ {
        result[k], result[n-1-k] = result[n-1-k], result[k]
    }
    
    return result
}

Go Implementation Notes: Go does not have a built-in reverse, so we manually reverse the slice. The carry and bit calculations mirror the Python implementation. Slice appending is used to dynamically build the result.

Worked Examples

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

Step i j total new bit carry result (reversed)
1 4 2 1+1+0=2 0 -1 [0]
2 3 1 1+0+(-1)=0 0 0 [0,0]
3 2 0 1+1+0=2 0 -1 [0,0,0]
4 1 -1 1+0+(-1)=0 0 0 [0,0,0,0]
5 0 -1 1+0+0=1 1 0 [0,0,0,0,1]

Reverse to [1,0,0,0,0].

Example 2: arr1 = [0], arr2 = [0] → result [0] after trivial addition.

Example 3: arr1 = [0], arr2 = [1] → result [1].

Complexity Analysis

Measure Complexity Explanation
Time O(max(n, m)) We iterate through the longer array once, handling all bits and carry.
Space O(max(n, m)) The result array may grow to at most one more than the longer input array due to carry propagation.

The algorithm scales linearly with input size and avoids large integer arithmetic, making it safe for large inputs.

Test Cases

# Provided examples
assert Solution().addNegabinary([1,1,1,1,1], [1,0,1]) == [1,0,0,0,0]  # normal addition
assert Solution().addNegabinary([0], [0]) == [0]                       # both zeros
assert Solution().addNegabinary([0], [1]) == [1]                       # zero + one

# Edge tests
assert Solution().addNegabinary([1], [1]) == [1,1,0]                   # 1+1 in negabinary
assert Solution().addNegabinary([1,0,1], [1,0,1]) == [1,1,1,1,0]       # same length addition
assert Solution().addNegabinary([1,1,0,1], [0]) == [1,1,0,1]           # adding zero
assert Solution().addNegabinary([1,1,1,1], [1]) == [1,0,0,0,1,1]       # carry propagation
Test Why
[1,1,1,1,1] + [1,0,1] Normal addition with multiple carries
[0] + [0] Both zeros, trivial output
[