Algorithm
Problem Name: 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.
Example 2:
Input: arr1 = [0], arr2 = [0] Output: [0]
Example 3:
Input: arr1 = [0], arr2 = [1] Output: [1]
Constraints:
1 <= arr1.length, arr2.length <= 1000arr1[i]andarr2[i]are0or1arr1andarr2have no leading zeros
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
int idxOne = arr1.length - 1;
int idxTwo = arr2.length - 1;
int carry = 0;
Stack stack = new Stack<>();
while (idxOne >= 0 || idxTwo >= 0 || carry != 0) {
int valOne = idxOne >= 0 ? arr1[idxOne--] : 0;
int valTwo = idxTwo >= 0 ? arr2[idxTwo--] : 0;
carry = valOne + valTwo + carry;
stack.push(carry & 1);
carry = -(carry >> 1);
}
while (!stack.isEmpty() && stack.peek() == 0) {
stack.pop();
}
int[] result = new int[stack.size()];
for (int i = 0; i < result.length; i++) {
result[i] = stack.pop();
}
return result.length == 0 ? new int[]{0} : result;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const addNegabinary = function(arr1, arr2) {
let ret = [];
arr1.reverse();
arr2.reverse();
let n = arr1.length,
m = arr2.length,
g = 0;
for (let i = 0; i < Math.max(n, m); i++) {
let s = g;
if (i < n) s += arr1[i];
if (i < m) s += arr2[i];
g = (s / -2) >> 0;
if (s + g * 2 < 0) g++;
ret.push(s + g * 2);
}
while (g) {
let s = g;
g = (s / -2) >> 0;
if (s + g * 2 < 0) g++;
ret.push(s + g * 2);
}
while (ret.length > 1 && ret[ret.length - 1] == 0) ret.pop();
ret.reverse();
return ret;
};
Input
Output