Adding Two Negabinary Numbers

Med

#1022Time: 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: 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.1 company

Patterns

Math

Data structures

Array

Companies

Grab

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1import java.math.BigInteger;2 3private BigInteger toDecimal(int[] arr) {4    BigInteger result = BigInteger.ZERO;5    BigInteger powerOfNegTwo = BigInteger.ONE;6    BigInteger negTwo = new BigInteger("-2");7    for (int i = arr.length - 1; i >= 0; i--) {8        if (arr[i] == 1) {9            result = result.add(powerOfNegTwo);10        }11        powerOfNegTwo = powerOfNegTwo.multiply(negTwo);12    }13    return result;14}

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

1BigInteger num1 = toDecimal(arr1);2BigInteger num2 = toDecimal(arr2);3BigInteger 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.

1private int[] fromDecimal(BigInteger n) {2    if (n.equals(BigInteger.ZERO)) {3        return new int[]{0};4    }5    java.util.List<Integer> list = new java.util.ArrayList<>();6    BigInteger negTwo = new BigInteger("-2");7    while (!n.equals(BigInteger.ZERO)) {8        BigInteger[] divAndRem = n.divideAndRemainder(negTwo);9        BigInteger quotient = divAndRem[0];10        BigInteger remainder = divAndRem[1];11        if (remainder.compareTo(BigInteger.ZERO) < 0) {12            remainder = remainder.add(BigInteger.valueOf(2));13            quotient = quotient.add(BigInteger.ONE);14        }15        list.add(remainder.intValue());16        n = quotient;17    }18    java.util.Collections.reverse(list);19    return list.stream().mapToInt(i -> i).toArray();20}

Complexity

Time

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

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.

Trade-offs

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.

This approach simulates the process of column-by-column addition directly on the negabinary numbers, much like performing addition by hand. It iterates from the least significant bit (rightmost) to the most significant bit (leftmost), calculating the sum and a carry at each position. The main distinction from standard binary addition is the unique logic for calculating and propagating the carry in a base -2 system.

Algorithm

1. Initialize two pointers, i and j, to point to the last element of arr1 and arr2 respectively.
1. Initialize a carry variable to 0 and a LinkedList<Integer> to store result bits.
1. Loop while i >= 0 or j >= 0 or carry != 0.
1. In each iteration, retrieve the current bits from arr1[i] and arr2[j]. If a pointer is out of bounds, the bit is considered 0. Decrement the pointers.
1. Calculate the sum of the two bits and the current carry.
1. The result bit for the current position is sum & 1. Add this bit to the front of the result list.
1. Calculate the new carry for the next position (to the left) using the formula carry = -(sum >> 1).
1. After the loop, the result list holds the sum in negabinary form, possibly with leading zeros.
1. Remove any leading zeros. If the result is all zeros, return [0].
1. Convert the final list to an integer array and return it.

Walkthrough

This method avoids conversions to other bases and works directly with the negabinary representation. It mimics manual addition.

We iterate from right to left, maintaining a carry. The sum at each position k is arr1[k] + arr2[k] + carry. The value at this position must be represented by a digit d_k (0 or 1) and a carry to the next position. The relationship is sum = d_k + (-2) * carry_new.

From this, we can derive the rules:

The digit d_k is sum mod 2. A simple way to compute this is sum & 1.
The new carry is carry_new = (sum - d_k) / (-2). This can be simplified. For any integer sum, (sum - (sum & 1)) is always an even number. Dividing by -2 is equivalent to dividing by 2 and negating. In Java, the bitwise right shift >> on sum effectively calculates floor(sum / 2). The expression -(sum >> 1) correctly computes the new carry for all possible sum values (-1, 0, 1, 2, 3).

For example:

If sum = 2 (1+1+0): d_k = 2 & 1 = 0. carry_new = -(2 >> 1) = -1.
If sum = -1 (0+0-1): d_k = -1 & 1 = 1. carry_new = -(-1 >> 1) = -(-1) = 1.

The algorithm proceeds until all input digits are processed and the carry becomes zero. Finally, any leading zeros in the result are removed.

1import java.util.LinkedList;2 3public int[] addNegabinary(int[] arr1, int[] arr2) {4    int i = arr1.length - 1;5    int j = arr2.length - 1;6    int carry = 0;7    LinkedList<Integer> result = new LinkedList<>();8 9    while (i >= 0 || j >= 0 || carry != 0) {10        int bit1 = (i >= 0) ? arr1[i--] : 0;11        int bit2 = (j >= 0) ? arr2[j--] : 0;12        int sum = bit1 + bit2 + carry;13        14        result.addFirst(sum & 1);15        carry = -(sum >> 1);16    }17 18    // Remove leading zeros19    int firstOneIndex = -1;20    for (int k = 0; k < result.size(); k++) {21        if (result.get(k) == 1) {22            firstOneIndex = k;23            break;24        }25    }26 27    if (firstOneIndex == -1) { // Result is 028        return new int[]{0};29    }30 31    // Convert LinkedList to array, skipping leading zeros32    int[] finalResult = new int[result.size() - firstOneIndex];33    for (int k = 0; k < finalResult.length; k++) {34        finalResult[k] = result.get(firstOneIndex + k);35    }36 37    return finalResult;38}

Complexity

Time

O(max(N, M)), where N and M are the lengths of the input arrays. The algorithm performs a single pass through the digits of the numbers.

Space

O(max(N, M)) to store the result. The space used for pointers and the carry is constant.

Trade-offs

Pros

Highly efficient with an optimal time complexity.
Avoids the overhead and complexity of large number libraries like BigInteger by working with small, constant-size integers.
It is a direct and elegant solution that operates within the problem's native negabinary representation.

Cons

The carry propagation logic, carry = -(sum >> 1), is non-intuitive compared to standard binary addition and requires a solid understanding of negabinary properties or careful derivation.

Solutions

Solution

1public class Solution {2    public int[] AddNegabinary(int[] arr1, int[] arr2) {3        int i = arr1.Length - 1, j = arr2.Length - 1;4        List < int > ans = new List < int > ();5        for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {6            int a = i < 0 ? 0 : arr1[i];7            int b = j < 0 ? 0 : arr2[j];8            int x = a + b + c;9            c = 0;10            if (x >= 2) {11                x -= 2;12                c -= 1;13            } else if (x == -1) {14                x = 1;15                c = 1;16            }17            ans.Add(x);18        }19        while (ans.Count > 1 && ans[ans.Count - 1] == 0) {20            ans.RemoveAt(ans.Count - 1);21        }22        ans.Reverse();23        return ans.ToArray();24    }25}

1class Solution {2public3  int[] addNegabinary(int[] arr1, int[] arr2) {4    int i = arr1.length - 1, j = arr2.length - 1;5    List<Integer> ans = new ArrayList<>();6    for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {7      int a = i < 0 ? 0 : arr1[i];8      int b = j < 0 ? 0 : arr2[j];9      int x = a + b + c;10      c = 0;11      if (x >= 2) {12        x -= 2;13        c -= 1;14      } else if (x == -1) {15        x = 1;16        c += 1;17      }18      ans.add(x);19    }20    while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {21      ans.remove(ans.size() - 1);22    }23    Collections.reverse(ans);24    return ans.stream().mapToInt(x->x).toArray();25  }26}

1class Solution {2public:3  vector<int> addNegabinary(vector<int> &arr1, vector<int> &arr2) {4    int i = arr1.size() - 1, j = arr2.size() - 1;5    vector<int> ans;6    for (int c = 0; i >= 0 || j >= 0 || c; --i, --j) {7      int a = i < 0 ? 0 : arr1[i];8      int b = j < 0 ? 0 : arr2[j];9      int x = a + b + c;10      c = 0;11      if (x >= 2) {12        x -= 2;13        c -= 1;14      } else if (x == -1) {15        x = 1;16        c += 1;17      }18      ans.push_back(x);19    }20    while (ans.size() > 1 && ans.back() == 0) {21      ans.pop_back();22    }23    reverse(ans.begin(), ans.end());24    return ans;25  }26};

1class Solution:2    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]: 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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem