Adding Two Negabinary Numbers
Problem
Given two numbers arr1 and arr2 written in base -2 (negabinary) as arrays of 0s and 1s, most significant digit first, return their sum in the same base -2 array format with no leading zeros. In base -2 the digit at position i contributes (-2)i, e.g. [1, 1, 0, 1] = (-2)3 + (-2)2 + (-2)0 = -8 + 4 + 1 = -3.
arr1 = [1, 1, 1, 1, 1], arr2 = [1, 0, 1][1, 0, 0, 0, 0]def add_negabinary(arr1, arr2):
i, j = len(arr1) - 1, len(arr2) - 1
carry, res = 0, []
while i >= 0 or j >= 0 or carry:
x = arr1[i] if i >= 0 else 0
y = arr2[j] if j >= 0 else 0
s = x + y + carry
res.append(s & 1) # digit is s mod 2
carry = -(s >> 1) # base -2: carry = -floor(s / 2)
i -= 1
j -= 1
while len(res) > 1 and res[-1] == 0:
res.pop() # strip leading zeros
return res[::-1]function addNegabinary(arr1, arr2) {
let i = arr1.length - 1, j = arr2.length - 1;
let carry = 0;
const res = [];
while (i >= 0 || j >= 0 || carry) {
const x = i >= 0 ? arr1[i] : 0;
const y = j >= 0 ? arr2[j] : 0;
const s = x + y + carry;
res.push(s & 1); // digit is s mod 2
carry = -(s >> 1); // base -2: carry = -floor(s / 2)
i--; j--;
}
while (res.length > 1 && res[res.length - 1] === 0) res.pop();
return res.reverse();
}class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
int i = arr1.length - 1, j = arr2.length - 1, carry = 0;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0 || carry != 0) {
int x = i >= 0 ? arr1[i] : 0;
int y = j >= 0 ? arr2[j] : 0;
int s = x + y + carry;
sb.append(s & 1); // digit is s mod 2
carry = -(s >> 1); // base -2: carry = -floor(s / 2)
i--; j--;
}
while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0')
sb.deleteCharAt(sb.length() - 1);
sb.reverse();
int[] res = new int[sb.length()];
for (int k = 0; k < res.length; k++) res[k] = sb.charAt(k) - '0';
return res;
}
}vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
int i = arr1.size() - 1, j = arr2.size() - 1, carry = 0;
vector<int> res;
while (i >= 0 || j >= 0 || carry) {
int x = i >= 0 ? arr1[i] : 0;
int y = j >= 0 ? arr2[j] : 0;
int s = x + y + carry;
res.push_back(s & 1); // digit is s mod 2
carry = -(s >> 1); // base -2: carry = -floor(s / 2)
i--; j--;
}
while (res.size() > 1 && res.back() == 0) res.pop_back();
reverse(res.begin(), res.end());
return res;
}Explanation
This is column addition just like normal binary, but the base is -2 instead of 2, which only changes how the carry behaves. We still add digit by digit from the rightmost (least significant) end.
At each column we add the two digits plus the incoming carry into s. The output digit is s & 1 (the value of s mod 2, always 0 or 1). The clever part is the new carry: because each position is worth -2 times the one to its left, the carry is -(s >> 1), that is the negative of floor(s / 2).
That negative carry can be 1, 0, or -1, so the loop must keep running while there are digits left or the carry is nonzero. This lets the result grow longer than either input when needed.
We build the answer least-significant first, so afterward we strip trailing zeros (which are the leading zeros once reversed) and reverse to put the most significant digit first.
Example: [1,1,1,1,1] is 11 and [1,0,1] is 5; their sum 16 must be written in base -2. The simulation produces [1,0,0,0,0], which indeed equals 16 since (-2)^4 = 16.