Adding Two Negabinary Numbers - Leetcode Solution

The problem "Adding Two Negabinary Numbers" on LeetCode is stated as follows:

Given two numbers arr1 and arr2 in negabinary representation, return the negabinary sum of the two numbers.

Negabinary is a base-2 system where the values of the digits can be -1, 0, or 1, instead of 0 or 1 in regular binary. For example, the negabinary representation of the number 3 is "11010".

To solve this problem, we can follow the following steps:

1. Convert the two negabinary numbers to decimal. We can do this by iterating through each digit of the numbers, starting from the least significant digit, and multiplying the value of the digit (which can be -1, 0, or 1) by the corresponding power of 2 (which can be 2^n where n is the position of the digit, or -2^n if n is odd). We can then add the results to get the decimal equivalents of the two numbers.

2. Add the decimal equivalents of the two numbers obtained in step 1.

3. Convert the decimal sum obtained in step 2 to negabinary representation. To do this, we can use the "division by -2" algorithm, similar to the "division by 2" algorithm used for converting decimal to binary. We repeatedly divide the sum by -2 and keep track of the remainder at each step. If the remainder is negative, we add 2 to it and set the next dividend to be equal to the current dividend plus 1. We continue this process until the quotient is zero and we have obtained the negabinary representation of the sum.

Here is the Python implementation of the above algorithm:

class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        # Convert the two negabinary numbers to decimal
        num1 = sum(arr1[i] * (-2)**i for i in range(len(arr1)))
        num2 = sum(arr2[i] * (-2)**i for i in range(len(arr2)))
        
        # Add the decimal equivalents of the two numbers
        decimal_sum = num1 + num2
        
        # Convert the sum to negabinary representation
        negabinary_sum = []
        while decimal_sum != 0:
            remainder = decimal_sum % -2
            decimal_sum //= -2
            if remainder < 0:
                remainder += 2
                decimal_sum += 1
            negabinary_sum.append(remainder)
        
        if not negabinary_sum:
            return [0]
        return negabinary_sum[::-1]

In the above implementation, we first convert the two negabinary numbers to decimal using list comprehension. We then add the decimal equivalents of the two numbers to get the decimal sum. Finally, we convert the decimal sum to negabinary representation using a while loop that implements the "division by -2" algorithm. The resulting negabinary sum is returned.

Note that we have to check if the negabinary sum is empty and return [0] in that case. This happens if both arr1 and arr2 are [0]. We also reverse the negabinary sum using list slicing to get the correct order of digits.

1