We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Adding Two Negabinary Numbers

Difficulty: Medium

Problem Description

Given two numbers arr1 and arr2 in base -2, return the result of adding them together. Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1. Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Key Insights

  • Numbers are represented in base -2, which means the powers of -2 are used for each bit.
  • The addition must handle carry appropriately, similar to binary addition.
  • The result must be returned in the same array format without leading zeros.

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

The solution involves simulating the addition of two numbers in base -2. We start from the least significant bit and move towards the most significant bit while managing a carry. We iterate through both arrays until we exhaust both. If the sum at any bit position exceeds 1, we account for the carry and adjust the result accordingly. Finally, we ensure the result does not have leading zeros.

Code Solutions

def addNegabinary(arr1, arr2):
    i, j = len(arr1) - 1, len(arr2) - 1
    carry = 0
    result = []

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

        result.append(carry & 1)  # Append the last bit of carry
        carry = -(carry >> 1)      # Update carry for base -2

    # Remove leading zeros and reverse the result
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    
    return result[::-1]
← Back to All Questions