LeetCode Solutions Blog

Adding Two Negabinary Numbers

Number: 1148

Difficulty: Medium

Paid? No

Companies: Grab

Problem Description

Given two numbers represented in base -2 as arrays of 0s and 1s (with the most significant bit first), return the result of adding these two negabinary numbers, also in array format without leading zeros.

Key Insights

Negabinary (base -2) behaves differently than binary (base 2), especially regarding carries.
Addition proceeds from the least significant digits to the most significant.
The carry value can be negative or positive and needs to be carefully updated.
The current digit is obtained with (sum mod 2) and the carry is updated as carry = -((sum - digit) / 2).

Space and Time Complexity

Time Complexity: O(max(n, m)), where n and m are the lengths of arr1 and arr2.
Space Complexity: O(max(n, m)) for storing the result.

Solution

We simulate the addition process from rightmost digits of arr1 and arr2. At each index, we calculate the sum by adding the corresponding digits and the current carry. The resulting digit is the remainder when divided by 2, and the carry is updated using the negabinary rule: carry = -((sum - digit) / 2). This process continues until all digits and the carry are processed. Finally, we remove any unnecessary leading zeros and reverse the result to return it in the correct order.

Code Solutions

# Python solution for adding two negabinary numbers

def addNegabinary(arr1, arr2):
    # Initialize result list and carry
    result = []
    carry = 0
    # Pointers for arr1 and arr2 starting from the least significant digit
    i = len(arr1) - 1
    j = len(arr2) - 1
    
    # Process all digits and any remaining carry
    while i >= 0 or j >= 0 or carry:
        # Get current digits; if index is out of bounds, use 0
        x = arr1[i] if i >= 0 else 0
        y = arr2[j] if j >= 0 else 0
        
        # Sum current digits with carry
        total = x + y + carry
        
        # Compute current digit as total mod 2 (ensuring non-negative remainder)
        digit = total & 1  # equivalent to total % 2
        result.append(digit)
        
        # Update carry based on negabinary addition rule
        carry = -((total - digit) // 2)
        
        # Move pointers to the next digit (to the left)
        i -= 1
        j -= 1
    
    # Remove excess leading zeros, ensuring at least one digit remains
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    
    # Reverse result to get the correct order (most significant digit first)
    return result[::-1]

# Example usage:
print(addNegabinary([1,1,1,1,1], [1,0,1]))  # Expected Output: [1,0,0,0,0]