Description
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] and arr2[i] are 0 or 1arr1 and arr2 have no leading zeros
Solutions
Solution 1
PythonJavaC++GoTypeScriptC#
class Solution:
def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
i, j = len(arr1) - 1, len(arr2) - 1
c = 0
ans = []
while i >= 0 or j >= 0 or c:
a = 0 if i < 0 else arr1[i]
b = 0 if j < 0 else arr2[j]
x = a + b + c
c = 0
if x >= 2:
x -= 2
c -= 1
elif x == -1:
x = 1
c += 1
ans.append(x)
i, j = i - 1, j - 1
while len(ans) > 1 and ans[-1] == 0:
ans.pop()
return ans[::-1](code-box)
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 >= 2) {
x -= 2;
c -= 1;
} else if (x == -1) {
x = 1;
c += 1;
}
ans.add(x);
}
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();
}
}(code-box)
class Solution {
public:
vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
int i = arr1.size() - 1, j = arr2.size() - 1;
vector<int> ans;
for (int c = 0; i >= 0 || j >= 0 || c; --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;
}
ans.push_back(x);
}
while (ans.size() > 1 && ans.back() == 0) {
ans.pop_back();
}
reverse(ans.begin(), ans.end());
return ans;
}
};(code-box)
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 >= 2 {
x -= 2
c -= 1
} else if x == -1 {
x = 1
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
}(code-box)
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 >= 2) {
x -= 2;
c -= 1;
} else if (x === -1) {
x = 1;
c += 1;
}
ans.push(x);
}
while (ans.length > 1 && ans[ans.length - 1] === 0) {
ans.pop();
}
return ans.reverse();
}(code-box)
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;
}
ans.Add(x);
}
while (ans.Count > 1 && ans[ans.Count - 1] == 0) {
ans.RemoveAt(ans.Count - 1);
}
ans.Reverse();
return ans.ToArray();
}
}(code-box)
