Jobs

Interviews

Discussions

Adding Two Negabinary Numbers

Medium

Grab

2 views

Topics:

ArraysTwo Pointers

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

Try coding it in LeetCode

Adding Two Negabinary Numbers

Medium

Grab

2 views

Topics:

ArraysTwo Pointers

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of `arr1` and `arr2`? Are they guaranteed to be non-empty?
Can `arr1` and `arr2` contain leading zeros? If so, should I remove them before calculating the sum?
Should the output negabinary representation also avoid leading zeros (except if the sum is zero itself)?
How should I handle the case where the result is zero? Should I return an empty array or an array containing a single zero?
Is it guaranteed that each element in `arr1` and `arr2` will be either 0 or 1?

Brute Force Solution

Approach

We want to add two numbers that are written in a special way using -2 instead of 2 as the base. The brute force strategy is like manually working through the addition, handling the carry-overs in this unusual system.

Here's how the algorithm would work step-by-step:

Start by lining up the two numbers as you would for regular addition, making sure to pad shorter numbers with leading zeros so they have the same length.
Begin adding the digits column by column, starting from the rightmost column.
For each column, add the two digits together, and also add any carry-over value from the previous column's calculation.
The result of adding the digits and the carry can be 0, 1, 2, or 3, or even a negative number if there was a negative carry.
If the result is 0 or 1, that's fine, and it becomes the digit in that column of the final answer. You'll likely have no carry in this case.
If the result is 2 or 3, or a negative number, you will need to adjust it and generate a carry-over value to the next column. Because we use -2 as the base, you may need to carry both a 1 and -1 to the next columns.
Continue this process for each column, including handling any carry-over values. Be careful to manage the carry in the unusual negabinary system.
Once you've processed all the columns, including any final carry-over, you'll have a negabinary representation of the sum.
You might need to remove any leading zeros to get the final answer.

Code Implementation

def adding_two_negabinary_numbers(first_number, second_number):
    maximum_length = max(len(first_number), len(second_number))
    first_number = first_number + [0] * (maximum_length - len(first_number))
    second_number = second_number + [0] * (maximum_length - len(second_number))

    carry = 0
    result = []

    for i in range(maximum_length):
        digit_sum = first_number[i] + second_number[i] + carry

        # Handle cases where digit sum is 2 or 3
        if digit_sum >= 2:
            result.append(digit_sum - 2)
            carry = -1

        # Handle cases where digit sum is negative.
        elif digit_sum < 0:
            result.append(digit_sum + 2)
            carry = 1

        else:
            result.append(digit_sum)
            carry = 0

    # Handle any remaining carry.
    if carry != 0:
        result.append(carry)

    # Remove leading zeros.
    while len(result) > 1 and result[-1] == 0:
        result.pop()

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the two negabinary numbers from right to left, performing addition and carry propagation at each position. The number of digits to process is proportional to the length, 'n', of the longer input negabinary number. The carry propagation logic within each iteration takes constant time. Therefore, the overall time complexity is determined by the single pass through the digits, resulting in a linear relationship with the input size n.

Space Complexity

O(N) – The space complexity is dominated by the potential need to store the resulting negabinary number. The resulting number can have at most N+2 digits, where N is the maximum length of the two input negabinary numbers after padding. Leading zeros might also be stored temporarily before being removed. Therefore, the algorithm uses auxiliary space proportional to the size of the input, N.

Optimal Solution

Approach

To add two numbers in negabinary (base -2), we simulate how you add regular binary numbers, but with special handling for carries. The core idea is to add the digits at each position and deal with any resulting value that is not a valid negabinary digit (0 or 1).

Here's how the algorithm would work step-by-step:

Start from the least significant digit (the rightmost digit) of both negabinary numbers, just like you do when adding regular numbers.
Add the corresponding digits at each position. Remember that a digit in negabinary can only be 0 or 1.
If the sum is 0 or 1, simply record that digit as the result for that position.
If the sum is 2, it is equivalent to -2 + 0 in base -2, meaning we need to subtract 2. We record 0 at the current position and carry over -1 two positions to the left (since (-2)^2 = 4, so -1 * 4 = -4 = -2 -2). We represent the carry as '11' two places over since -2 + -2 = -4, thus we compensate by adding 11 to the correct spots
If the sum is 3, it means 1 + 1 + 1. Because 3 is equivalent to -2 + 1, we put down 1 at the current position and carry -1 two positions over (two positions to the left). In this case, the carry of -1 two spots over is represented as '11'
If the sum is -1, meaning 0 + 0 - 1, or potentially dealing with carry situations. We need to represent -1 in negabinary. Since -1 is equivalent to 1 + (-2) which is `11` in base -2, we record `1` at the current position and add a `1` to the next higher spot.
Continue these steps until you have processed all digits from both numbers and any remaining carries. If there are carries left over after processing the digits, add enough leading zeroes to the number before adding the carry.
Remove any leading zeros from the final result, except if the result is zero, in which case keep one zero.

Code Implementation

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

    while i >= 0 or j >= 0 or carry != 0:
        digit1 = arr1[i] if i >= 0 else 0
        digit2 = arr2[j] if j >= 0 else 0

        current_sum = digit1 + digit2 + carry

        if current_sum == 0:
            result.append(0)
            carry = 0

        elif current_sum == 1:
            result.append(1)
            carry = 0

        elif current_sum == 2:
            # 2 in negabinary is '110', so we carry -1.
            result.append(0)
            carry = -1

        elif current_sum == 3:
            # 3 in negabinary is '111', so we carry -1.
            result.append(1)
            carry = -1

        elif current_sum == -1:
            # -1 in negabinary is '11', so we carry 1.
            result.append(1)
            carry = 1

        i -= 1
        j -= 1

    # Reverse the result to get the correct order.
    result.reverse()

    # Removing leading zeros
    leading_zero_index = 0
    while leading_zero_index < len(result) - 1 and result[leading_zero_index] == 0:
        leading_zero_index += 1

    final_result = result[leading_zero_index:]

    return final_result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the two input negabinary numbers a and b, and the carry values. The number of iterations is proportional to the maximum length of the two input arrays and the carry propagation. Because, in the worst case, the algorithm needs to iterate over the entire length of both input arrays to perform the addition and handle carries, the time complexity is directly proportional to the maximum length of the inputs, n. The carry propagation at most adds a constant number of operations per digit. Removing leading zeros also takes O(n) time in the worst case.

Space Complexity

O(N) – The algorithm potentially needs to store the result in a new list, which in the worst case can have a size proportional to the sum of the lengths of the two input negabinary numbers (or slightly larger due to carries), where N is the maximum length between the two input arrays. Intermediate carries might add additional digits to the result. Therefore, the auxiliary space needed to store the result grows linearly with the input size, resulting in O(N) space complexity. Leading zeros removal does not affect the overall space complexity.

Edge Cases

Case	How to Handle
Both input arrays are empty	Return an array containing only 0, since 0 + 0 = 0 in any base.
One input array is empty, the other is not	Return the non-empty array after removing any leading zeros.
Input arrays containing only zeros	Return an array containing only 0 to represent the sum.
The result has leading zeros after the addition	Remove leading zeros from the result array before returning it.
The sum results in a long sequence of 1s requiring multiple carry operations	The carry logic must handle cascading carries correctly until no further carries are needed.
One input is much longer than the other	The algorithm should correctly handle different array lengths by padding the shorter array implicitly with zeros.
Result is zero after removing leading zeros, but initial calculation yielded [0,0,0]	Return [0] after stripping leading zeros in this case.
Large inputs causing potential memory or time constraints	The solution should scale linearly with the size of the input arrays; if extremely large, consider generator-based approach.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of `arr1` and `arr2`? Are they guaranteed to be non-empty?
Can `arr1` and `arr2` contain leading zeros? If so, should I remove them before calculating the sum?
Should the output negabinary representation also avoid leading zeros (except if the sum is zero itself)?
How should I handle the case where the result is zero? Should I return an empty array or an array containing a single zero?
Is it guaranteed that each element in `arr1` and `arr2` will be either 0 or 1?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by lining up the two numbers as you would for regular addition, making sure to pad shorter numbers with leading zeros so they have the same length.
Begin adding the digits column by column, starting from the rightmost column.
For each column, add the two digits together, and also add any carry-over value from the previous column's calculation.
The result of adding the digits and the carry can be 0, 1, 2, or 3, or even a negative number if there was a negative carry.
If the result is 0 or 1, that's fine, and it becomes the digit in that column of the final answer. You'll likely have no carry in this case.
If the result is 2 or 3, or a negative number, you will need to adjust it and generate a carry-over value to the next column. Because we use -2 as the base, you may need to carry both a 1 and -1 to the next columns.
Continue this process for each column, including handling any carry-over values. Be careful to manage the carry in the unusual negabinary system.
Once you've processed all the columns, including any final carry-over, you'll have a negabinary representation of the sum.
You might need to remove any leading zeros to get the final answer.

Code Implementation

def adding_two_negabinary_numbers(first_number, second_number):
    maximum_length = max(len(first_number), len(second_number))
    first_number = first_number + [0] * (maximum_length - len(first_number))
    second_number = second_number + [0] * (maximum_length - len(second_number))

    carry = 0
    result = []

    for i in range(maximum_length):
        digit_sum = first_number[i] + second_number[i] + carry

        # Handle cases where digit sum is 2 or 3
        if digit_sum >= 2:
            result.append(digit_sum - 2)
            carry = -1

        # Handle cases where digit sum is negative.
        elif digit_sum < 0:
            result.append(digit_sum + 2)
            carry = 1

        else:
            result.append(digit_sum)
            carry = 0

    # Handle any remaining carry.
    if carry != 0:
        result.append(carry)

    # Remove leading zeros.
    while len(result) > 1 and result[-1] == 0:
        result.pop()

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start from the least significant digit (the rightmost digit) of both negabinary numbers, just like you do when adding regular numbers.
Add the corresponding digits at each position. Remember that a digit in negabinary can only be 0 or 1.
If the sum is 0 or 1, simply record that digit as the result for that position.
If the sum is 2, it is equivalent to -2 + 0 in base -2, meaning we need to subtract 2. We record 0 at the current position and carry over -1 two positions to the left (since (-2)^2 = 4, so -1 * 4 = -4 = -2 -2). We represent the carry as '11' two places over since -2 + -2 = -4, thus we compensate by adding 11 to the correct spots
If the sum is 3, it means 1 + 1 + 1. Because 3 is equivalent to -2 + 1, we put down 1 at the current position and carry -1 two positions over (two positions to the left). In this case, the carry of -1 two spots over is represented as '11'
If the sum is -1, meaning 0 + 0 - 1, or potentially dealing with carry situations. We need to represent -1 in negabinary. Since -1 is equivalent to 1 + (-2) which is `11` in base -2, we record `1` at the current position and add a `1` to the next higher spot.
Continue these steps until you have processed all digits from both numbers and any remaining carries. If there are carries left over after processing the digits, add enough leading zeroes to the number before adding the carry.
Remove any leading zeros from the final result, except if the result is zero, in which case keep one zero.

Code Implementation

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

    while i >= 0 or j >= 0 or carry != 0:
        digit1 = arr1[i] if i >= 0 else 0
        digit2 = arr2[j] if j >= 0 else 0

        current_sum = digit1 + digit2 + carry

        if current_sum == 0:
            result.append(0)
            carry = 0

        elif current_sum == 1:
            result.append(1)
            carry = 0

        elif current_sum == 2:
            # 2 in negabinary is '110', so we carry -1.
            result.append(0)
            carry = -1

        elif current_sum == 3:
            # 3 in negabinary is '111', so we carry -1.
            result.append(1)
            carry = -1

        elif current_sum == -1:
            # -1 in negabinary is '11', so we carry 1.
            result.append(1)
            carry = 1

        i -= 1
        j -= 1

    # Reverse the result to get the correct order.
    result.reverse()

    # Removing leading zeros
    leading_zero_index = 0
    while leading_zero_index < len(result) - 1 and result[leading_zero_index] == 0:
        leading_zero_index += 1

    final_result = result[leading_zero_index:]

    return final_result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input arrays are empty	Return an array containing only 0, since 0 + 0 = 0 in any base.
One input array is empty, the other is not	Return the non-empty array after removing any leading zeros.
Input arrays containing only zeros	Return an array containing only 0 to represent the sum.
The result has leading zeros after the addition	Remove leading zeros from the result array before returning it.
The sum results in a long sequence of 1s requiring multiple carry operations	The carry logic must handle cascading carries correctly until no further carries are needed.
One input is much longer than the other	The algorithm should correctly handle different array lengths by padding the shorter array implicitly with zeros.
Result is zero after removing leading zeros, but initial calculation yielded [0,0,0]	Return [0] after stripping leading zeros in this case.
Large inputs causing potential memory or time constraints	The solution should scale linearly with the size of the input arrays; if extremely large, consider generator-based approach.