{x}
blog image

Adding Two Negabinary Numbers

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.

 

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Example 2:

Input: arr1 = [0], arr2 = [0]
Output: [0]

Example 3:

Input: arr1 = [0], arr2 = [1]
Output: [1]

 

Constraints:

  • 1 <= arr1.length, arr2.length <= 1000
  • arr1[i] and arr2[i] are 0 or 1
  • arr1 and arr2 have no leading zeros

Solution Explanation: Adding Two Negabinary Numbers

This problem involves adding two numbers represented in negabinary (base -2) format. The input is given as two arrays of 0s and 1s, representing the digits of the negabinary numbers. The solution needs to perform the addition and return the result in the same negabinary format, without leading zeros.

Approach

The core idea is to simulate the addition process similar to how we add numbers in base 10, but with the rules of negabinary arithmetic. Key differences from base-10 addition include:

  1. Carry: When the sum of digits (plus carry) is greater than or equal to 2, we subtract 2 and carry -1. If the sum is -1, we set the digit to 1 and carry 1.

  2. Negabinary Representation: Each digit represents a power of -2. For example, [1, 0, 1] represents (-2)² + (-2)⁰ = 4 + 1 = 5.

  3. Result Formatting: The final result might contain leading zeros, which need to be removed.

Algorithm

The algorithm iterates through the input arrays from right to left (least significant bit to most significant bit), performing the following steps:

  1. Initialization: Initialize carry to 0. Use pointers i and j to traverse arr1 and arr2.
  2. Digit Addition: At each position, sum the digits from arr1 and arr2 (handling cases where one array is shorter than the other), and add the carry.
  3. Carry Handling: Apply the negabinary rules to handle the sum:
    • If the sum is greater than or equal to 2, subtract 2 and set the carry to -1.
    • If the sum is -1, set the digit to 1 and set the carry to 1.
  4. Append Digit: Append the resulting digit to the ans array.
  5. Iteration: Continue until both arrays are traversed and the carry is 0.
  6. Remove Leading Zeros: Remove trailing zeros from ans.
  7. Reverse: Reverse ans because we added the digits from right to left.

Time and Space Complexity

  • Time Complexity: O(max(m, n)), where 'm' and 'n' are the lengths of arr1 and arr2. This is because we iterate through the arrays once.
  • Space Complexity: O(max(m, n)), in the worst case, the length of the resulting array ans can be at most one element longer than the longest input array. The space used by ans dominates the space complexity.

Code (Python)

def addNegabinary(arr1, arr2):
    i, j = len(arr1) - 1, len(arr2) - 1
    c = 0
    ans = []
    while i >= 0 or j >= 0 or c:
        a = 0 if i < 0 else arr1[i]
        b = 0 if j < 0 else arr2[j]
        x = a + b + c
        c = 0
        if x >= 2:
            x -= 2
            c -= 1
        elif x == -1:
            x = 1
            c += 1
        ans.append(x)
        i, j = i - 1, j - 1
    while len(ans) > 1 and ans[-1] == 0:
        ans.pop()
    return ans[::-1]

The code in other languages follows the same logic, with only syntactic differences. The crucial part is the negabinary addition logic within the loop and the post-processing steps to remove leading zeros and reverse the result.