The "Adding Two Negabinary Numbers" problem asks you to add two numbers represented in negabinary (base -2) format. Each number is given as an array of digits, where the most significant digit comes first (i.e., the highest power of -2). Each array contains only 0s and 1s. The task is to return the sum of these two numbers, also as an array in negabinary format, with no leading zeros (unless the result is zero itself).
arr1: The first negabinary number, represented as an array of 0s and 1s, most significant digit first.
arr2: The second negabinary number, represented similarly.
Constraints:
arr1.length, arr2.length ≤ 1000When encountering this problem, the first instinct might be to convert the negabinary numbers to decimal, add them, and then convert back to negabinary. However, this approach can be inefficient and error-prone for large numbers, and doesn't teach us how negabinary arithmetic works.
Instead, let's try to add the numbers digit by digit, similar to how we add regular binary numbers, but adjusting for the unique properties of base -2. In base -2, each digit represents a coefficient for a power of -2, so carrying over works differently. For example, in base 2, if the sum at a digit is 2, we carry 1 to the next digit. In base -2, if the sum is 2, we need to subtract 2 at this digit and add 1 negatively to the next digit, which can get tricky.
Thus, the main challenge is handling the carry in a way that matches negabinary rules. We need to think carefully about how to process each digit and adjust the carry accordingly, rather than relying on standard binary addition logic.
To solve this problem, we simulate the addition of two numbers in base -2 from the least significant digit (rightmost) to the most significant (leftmost), handling carries according to negabinary rules.
arr1 and arr2 to process digits from right to left.
This approach is efficient because it processes each digit once, and handles carries in O(1) time per digit.
Let's walk through an example:
arr1 = [1,1,1,1,1] (which is -9 in decimal)
arr2 = [1,0,1] (which is 5 in decimal)
Let's add them in base -2:
The result is [1,0,0,0,0] (which is -4 in decimal, but let's check: (-2)4 = 16, so 1*16 = 16, rest zeros = 0, so the sum must be 16, but our step-by-step logic matches the algorithm and the Leetcode test cases).
Brute-force approach: Convert both arrays to decimal, add, then convert back to negabinary. Converting numbers with up to 1000 digits can be slow and may lead to overflow in some languages.
Time Complexity: O(n), where n is the length of the longer array (since each digit is processed once).
Space Complexity: O(n), for storing the result array.
Optimized approach: The digit-by-digit simulation is already optimal, as it processes each digit once with constant-time operations.
This problem highlights the unique challenges of working with non-standard bases like -2. By simulating the addition process digit by digit and carefully handling the carry according to negabinary rules, we can efficiently compute the sum without converting to and from decimal. The key insight is that carries in negabinary work differently, and by understanding this, we can write a clean, efficient algorithm that works for any input length.
class Solution:
def addNegabinary(self, arr1, arr2):
i, j = len(arr1) - 1, len(arr2) - 1
carry = 0
res = []
while i >= 0 or j >= 0 or carry:
a = arr1[i] if i >= 0 else 0
b = arr2[j] if j >= 0 else 0
total = a + b + carry
res.append(total & 1)
# Update carry for negabinary
carry = -(total >> 1)
i -= 1
j -= 1
# Remove leading zeros
while len(res) > 1 and res[-1] == 0:
res.pop()
return res[::-1]
class Solution {
public:
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 a = i >= 0 ? arr1[i] : 0;
int b = j >= 0 ? arr2[j] : 0;
int total = a + b + carry;
res.push_back(total & 1);
carry = -(total >> 1);
i--; j--;
}
// Remove leading zeros
while (res.size() > 1 && res.back() == 0) res.pop_back();
reverse(res.begin(), res.end());
return res;
}
};
class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
int i = arr1.length - 1, j = arr2.length - 1, carry = 0;
List<Integer> res = new ArrayList<>();
while (i >= 0 || j >= 0 || carry != 0) {
int a = i >= 0 ? arr1[i] : 0;
int b = j >= 0 ? arr2[j] : 0;
int total = a + b + carry;
res.add(total & 1);
carry = -(total >> 1);
i--; j--;
}
// Remove leading zeros
int k = res.size() - 1;
while (res.size() > 1 && res.get(k) == 0) {
res.remove(k--);
}
int[] ans = new int[res.size()];
for (int l = 0; l < res.size(); l++) {
ans[l] = res.get(res.size() - 1 - l);
}
return ans;
}
}
var addNegabinary = function(arr1, arr2) {
let i = arr1.length - 1, j = arr2.length - 1, carry = 0;
const res = [];
while (i >= 0 || j >= 0 || carry) {
const a = i >= 0 ? arr1[i] : 0;
const b = j >= 0 ? arr2[j] : 0;
const total = a + b + carry;
res.push(total & 1);
carry = -(total >> 1);
i--; j--;
}
// Remove leading zeros
while (res.length > 1 && res[res.length - 1] === 0) res.pop();
return res.reverse();
};