Adding Two Negabinary Numbers
给两个以-2为base的数字, 用数字表示, 求他们的合. 这个题和adding binary number那个题一样.
class Solution {
public int[] addNegabinary(int[] arr1, int[] arr2) {
if (arr1.length == 0) {
return arr2;
}
if (arr2.length == 0) {
return arr1;
}
int i = arr1.length - 1;
int j = arr2.length - 1;
int carry = 0;
List<Integer> list = new ArrayList<>();
while (i >= 0 && j >= 0) {
int k = arr1[i] + arr2[j] + carry;
list.add((k + 2) % 2);
carry = ((k + 2) % 2 - k) / 2;
i--;
j--;
}
while (i >= 0) {
int k = arr1[i] + carry;
list.add((k + 2) % 2);
carry = ((k + 2) % 2 - k) / 2;
i--;
}
while (j >= 0) {
int k = arr2[j] + carry;
list.add((k + 2) % 2);
carry = ((k + 2) % 2 - k) / 2;
j--;
}
while (carry != 0) {
list.add((carry + 2) % 2);
carry = ((carry + 2) % 2 - carry) / 2;
}
int m = list.size() - 1;
while (list.get(m) == 0 && m > 0) {
m--;
}
int[] result = new int[m + 1];
while (m >= 0) {
result[result.length - m - 1] = list.get(m);
m--;
}
return result;
}
}