Formatted question description: https://leetcode.ca/all/1073.html

1073. Adding Two Negabinary Numbers (Medium)

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. 1 <= arr1.length <= 1000
2. 1 <= arr2.length <= 1000
3. arr1 and arr2 have no leading zeros
4. arr1[i] is 0 or 1
5. arr2[i] is 0 or 1

Solution 1.

When adding two numbers in base 2 I use a variable carry to store the carryover.

Assume we are adding two bits a, b and carry. The sum can be 0, 1, 2, 3, and the leftover bit value is sum % 2 and the new value of carry is sum / 2.

Let’s try the same approach for this problem.

Assume the current bit represents k = (-2)^n, (n >= 0).

• Consider carry = 0, sum can be 0, 1, 2.
• When sum = 0 or 1, leftover = sum, carry = 0.
• When sum = 2, the value is 2k = -1 * (-2k), so it’s the same as leftover = 1, carry = -1
• Consider carry = -1, sum can be -1, 0, 1.
• For the new case sum = -1, the value is -k = -2k + k, so it’s the same as leftover = 1, carry = 1.
• Consider carry = 1, sum can be 1, 2, 3.
• For the new case sum = 3, the value is 3k = -1 * (-2k) + k, so it’s the same as leftover = 1, carry = -1.

Now we’ve considerred all cases. In sum:

sum|leftover|carry|

|—|— -1|1|1 0|0|0 1|1|0 2|0|-1 3|1|-1

The pattern is:

leftover = (sum + 2) % 2
carry = 1 - (sum + 2) / 2


Or

leftover = sum & 1
carry = -(sum >> 1)

// OJ: https://leetcode.com/problems/adding-two-negabinary-numbers/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> addNegabinary(vector<int>& A, vector<int>& B) {
vector<int> ans;
for (int i = A.size() - 1, j = B.size() - 1, carry = 0; i >= 0 || j >= 0 || carry;) {
if (i >= 0) carry += A[i--];
if (j >= 0) carry += B[j--];
ans.push_back(carry & 1);
carry = -(carry >> 1);
}
while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
reverse(ans.begin(), ans.end());
return ans;
}
};

• class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
int length1 = arr1.length, length2 = arr2.length;
int sumLength = Math.max(length1, length2) + 2;
int[] arr1Ext = new int[sumLength];
System.arraycopy(arr1, 0, arr1Ext, sumLength - length1, length1);
int[] arr2Ext = new int[sumLength];
System.arraycopy(arr2, 0, arr2Ext, sumLength - length2, length2);
int[] sumArr = new int[sumLength];
for (int i = sumLength - 1; i > 0; i--) {
sumArr[i] += arr1Ext[i] + arr2Ext[i];
int carry = sumArr[i] >> 1;
sumArr[i] -= carry * 2;
sumArr[i - 1] -= carry;
}
int startIndex = sumLength - 1;
for (int i = 0; i < sumLength; i++) {
if (sumArr[i] != 0) {
startIndex = i;
break;
}
}
int trimLength = sumLength - startIndex;
int[] sumArrTrim = new int[trimLength];
System.arraycopy(sumArr, startIndex, sumArrTrim, 0, trimLength);
return sumArrTrim;
}
}

############

class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
int i = arr1.length - 1, j = arr2.length - 1;
List<Integer> ans = new ArrayList<>();
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 > 1) {
x -= 2;
c -= 1;
}
if (x < 0) {
x += 2;
c += 1;
}
}
while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
ans.remove(ans.size() - 1);
}
Collections.reverse(ans);
return ans.stream().mapToInt(x -> x).toArray();
}
}

• // OJ: https://leetcode.com/problems/adding-two-negabinary-numbers/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> addNegabinary(vector<int>& A, vector<int>& B) {
vector<int> ans;
for (int i = A.size() - 1, j = B.size() - 1, carry = 0; i >= 0 || j >= 0 || carry;) {
if (i >= 0) carry += A[i--];
if (j >= 0) carry += B[j--];
ans.push_back(carry & 1);
carry = -(carry >> 1);
}
while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
reverse(ans.begin(), ans.end());
return ans;
}
};

• # 1073. Adding Two Negabinary Numbers

class Solution:
def addNegabinary(self, A: List[int], B: List[int]) -> List[int]:
res = []
carry = 0

while A or B or carry:
carry += (A or [0]).pop() + (B or [0]).pop()
res.append(carry & 1)
carry = -(carry >> 1)

while len(res) > 1 and res[-1] == 0: res.pop()

return res[::-1]


• func addNegabinary(arr1 []int, arr2 []int) (ans []int) {
i, j := len(arr1)-1, len(arr2)-1
for c := 0; i >= 0 || j >= 0 || c != 0; i, j = i-1, j-1 {
x := c
if i >= 0 {
x += arr1[i]
}
if j >= 0 {
x += arr2[j]
}
c = 0
if x > 1 {
x -= 2
c -= 1
}
if x < 0 {
x += 2
c += 1
}
ans = append(ans, x)
}
for len(ans) > 1 && ans[len(ans)-1] == 0 {
ans = ans[:len(ans)-1]
}
for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return ans
}

• function addNegabinary(arr1: number[], arr2: number[]): number[] {
let i = arr1.length - 1,
j = arr2.length - 1;
const ans: number[] = [];
for (let c = 0; i >= 0 || j >= 0 || c; --i, --j) {
const a = i < 0 ? 0 : arr1[i];
const b = j < 0 ? 0 : arr2[j];
let x = a + b + c;
c = 0;
if (x > 1) {
x -= 2;
c -= 1;
}
if (x < 0) {
x += 2;
c += 1;
}
ans.push(x);
}
while (ans.length > 1 && ans[ans.length - 1] === 0) {
ans.pop();
}
return ans.reverse();
}


• 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;
}