Adding Two Negabinary Numbers

MEDIUM

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.

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

Approaches

Checkout 2 different approaches to solve Adding Two Negabinary Numbers. Click on different approaches to view the approach and algorithm in detail.

Convert to Decimal, Add, and Convert Back

This approach follows a straightforward, multi-step process. First, it converts the two negabinary numbers from their array format into standard base-10 (decimal) integers. Since the values can become very large, java.math.BigInteger is used to prevent overflow. After conversion, the two decimal numbers are added together. Finally, the resulting sum is converted from its decimal representation back into the negabinary array format.

Algorithm

1. Implement a helper function toDecimal that takes a negabinary array and converts it to its java.math.BigInteger decimal equivalent. This is done by iterating through the array and summing up arr[i] * (-2)^power.
1. Implement a second helper function fromDecimal that converts a BigInteger back to a negabinary array. This involves a loop where in each step, the number is divided by -2, and the remainder is taken as the next digit. A special adjustment is needed if the remainder is negative.
1. In the main function, use toDecimal to convert both input arrays arr1 and arr2 into BigIntegers.
1. Add these two BigIntegers using the add method.
1. Pass the resulting sum to the fromDecimal function to get the final negabinary array.
1. Return the result.

The core idea is to switch from the negabinary system to the familiar decimal system to perform the addition, and then switch back.

Step 1: Negabinary to Decimal Conversion A function is created to convert an array like [1,1,0,1] to its decimal value. This is calculated as 1*(-2)^3 + 1*(-2)^2 + 0*(-2)^1 + 1*(-2)^0 = -8 + 4 + 0 + 1 = -3. We must use BigInteger to handle the large numbers that can arise from arrays up to 1000 elements long.

import java.math.BigInteger;

private BigInteger toDecimal(int[] arr) {
    BigInteger result = BigInteger.ZERO;
    BigInteger powerOfNegTwo = BigInteger.ONE;
    BigInteger negTwo = new BigInteger("-2");
    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] == 1) {
            result = result.add(powerOfNegTwo);
        }
        powerOfNegTwo = powerOfNegTwo.multiply(negTwo);
    }
    return result;
}

Step 2: Addition The two BigIntegers obtained from step 1 are simply added together.

BigInteger num1 = toDecimal(arr1);
BigInteger num2 = toDecimal(arr2);
BigInteger sum = num1.add(num2);

Step 3: Decimal to Negabinary Conversion This is the reverse of step 1. We convert the decimal sum back to a negabinary array. The standard algorithm is repeated division by the base (-2) and recording the remainders. However, standard remainders can be negative. We need remainders to be 0 or 1. If a remainder is negative (-1), we adjust it to 1 and add 1 to the quotient to compensate.

private int[] fromDecimal(BigInteger n) {
    if (n.equals(BigInteger.ZERO)) {
        return new int[]{0};
    }
    java.util.List<Integer> list = new java.util.ArrayList<>();
    BigInteger negTwo = new BigInteger("-2");
    while (!n.equals(BigInteger.ZERO)) {
        BigInteger[] divAndRem = n.divideAndRemainder(negTwo);
        BigInteger quotient = divAndRem[0];
        BigInteger remainder = divAndRem[1];
        if (remainder.compareTo(BigInteger.ZERO) < 0) {
            remainder = remainder.add(BigInteger.valueOf(2));
            quotient = quotient.add(BigInteger.ONE);
        }
        list.add(remainder.intValue());
        n = quotient;
    }
    java.util.Collections.reverse(list);
    return list.stream().mapToInt(i -> i).toArray();
}

Complexity Analysis

Time Complexity: O((max(N, M))^2). The conversion steps involve loops where `BigInteger` multiplication and division are performed. These operations are not constant time; their complexity depends on the number of bits in the operands, which is proportional to the array lengths.Space Complexity: O(max(N, M)), where N and M are the lengths of the input arrays. This space is used to store the `BigInteger` representations and the final result array.

Pros and Cons

Pros:

The approach is conceptually simple, breaking the problem into distinct, understandable steps: convert, add, convert back.
It leverages the powerful and well-tested BigInteger class, abstracting away the complexities of large number arithmetic.

Cons:

Significantly less efficient due to the computational overhead of BigInteger arithmetic, especially for multiplication and division operations.
The conversion from decimal back to negabinary requires careful handling of negative remainders, which can be complex and error-prone.

Code Solutions

Checking out 4 solutions in different languages for Adding Two Negabinary Numbers. Click on different languages to view the code.

public class Solution {
    public int[] AddNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.Length - 1, j = arr2.Length - 1;
        List < int > ans = new List < int > ();
        for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {
            int a = i < 0 ? 0 : arr1[i];
            int b = j < 0 ? 0 : arr2[j];
            int x = a + b + c;
            c = 0;
            if (x >= 2) {
                x -= 2;
                c -= 1;
            } else if (x == -1) {
                x = 1;
                c = 1;
            }
            ans.Add(x);
        }
        while (ans.Count > 1 && ans[ans.Count - 1] == 0) {
            ans.RemoveAt(ans.Count - 1);
        }
        ans.Reverse();
        return ans.ToArray();
    }
}

Video Solution

Watch the video walkthrough for Adding Two Negabinary Numbers

Patterns:

Math

Data Structures:

Array

Companies:

Grab |