Adding Two Negabinary Numbers

LeetCode Q 1073 - 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.

Note:

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

Solution

Solution 1: Not Correct

First transform two number to 10-base number and obtain the sum. Then transform the 10-base sum to -2-base int array.

This method is not correct. Since the number may be larger than Long.MAX_VALUE.

Code:

private static final int BASE = -2;

public int[] addNegabinary(int[] arr1, int[] arr2) {
  long sum = transformTo10(arr1) + transformTo10(arr2);
  return transformToN2(sum);
}

private long transformTo10(int[] arr) {
  long res = 0;
  for (int i = 0; i < arr.length; i++) {
    res = BASE * res + arr[i]; 
  }
  return res;
}

private int[] transformToN2(long num) {
  List<Integer> list = new ArrayList<>();
  
  while(num != 0) {
    int remainder = (int) (num % BASE);
    num /= BASE;
    if (remainder < 0) {
      remainder += Math.abs(BASE);
      num++;
    }
    list.add(0, remainder);
  }

  if (list.size() == 0) return new int[]{0};

  int[] res = new int[list.size()];
  int index = 0;
  for (int i: list)
    res[index++] = i;

  return res;
}

Solution 2:

Get idea from wikipedia

Adding negabinary numbers proceeds bitwise, starting from the least significant bits; the bits from each addend are summed with carry from the previous bit(0 at the LSB). This sum is then decomposed into an output bit and carry for the next iteration as shown in the table:

codes:

private static final int BASE = -2;

public int[] addNegabinary(int[] arr1, int[] arr2) {
  List<Integer> list = new ArrayList<>();
  int carry = 0, i = arr1.length - 1, j = arr2.length - 1;

  while (i >= 0 || j >= 0 || carry != 0) {
    int sum = carry;
    sum += i >= 0 ? arr1[i] : 0;
    sum += j >= 0 ? arr2[j] : 0;
    list.add(0, Math.abs(sum % BASE));
    carry = sum < 0 ? 1 : (sum <= 1 ? 0 : -1);
  }

  int leadingZeros = 0;
  for (int m = 0; m < list.size(); m++) {
    if (list.get(m) != 0) break;
    leadingZeros++;
  }

  if (list.size() - leadingZeros == 0) return new int[]{0};

  int[] res = new int[list.size() - leadingZeros];
  int index = 0;
  for (int n = leadingZeros; n < list.size(); n++) {
    res[index++] = list.get(n);
  }

  return res;
}