【LetMeFly】1073.负二进制数相加

力扣题目链接：https://leetcode.cn/problems/adding-two-negabinary-numbers/

给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。

数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。

返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。

示例 1：

输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
输出：[1,0,0,0,0]
解释：arr1 表示 11，arr2 表示 5，输出表示 16 。

示例 2：

输入：arr1 = [0], arr2 = [0]
输出：[0]

示例 3：

输入：arr1 = [0], arr2 = [1]
输出：[1]

提示：

1 <= arr1.length, arr2.length <= 1000
arr1[i] 和 arr2[i] 都是 0 或 1
arr1 和 arr2 都没有前导0

方法一：模拟

使用一个变量 $c$ 来存放加法的进位。我们从最低位开始遍历两个数组，记两个数组的当前元素分别为 $a$ 和 $b$ 。令 $x = a + b + c$ 。

若 $x\geq 2$ ，则 $x - = 2, c = - 1$ ，即逢 $2$ 进 $- 1$ （后面会解释）
若 $x = - 1$ ，则 $x = 1, c = 1$
否则， $c = 0$ （不产生进位）

将 $x$ 的最终值加入到答案数组中，继续处理下一位。

最终将答案数组翻转并去除前导零即可。

原因解释：

首先假设上述方法正确，因两个 $0$ 或 $1$ 相加的结果在 $0$ 到 $2$ 之间，进位 $c$ 的范围在 $- 1$ 到 $1$ 之间，所以 $x = a + b + c$ 的范围在 $- 1$ 到 $3$ 之间。

若 $x = 2$ 或 $x = 3$ ，因为负2进制每一位的范围是 $0$ 到 $1$ ，所以 $x$ 需要进位。记进位后的数为 $x_{final}$ ，则有 $x=2+x_{final}$ 。

$\begin{align*} x\times(-2)^{i}& =(2+x_{final})\times(-2)^{i}\\ &=2\times(-2)^i+x_{final}\times(-2)^i \\ &=(-1)\times(-2)\times(-2)^i+x_{final}\times(-2)^i \\ &=(-1)\times(-2)^{i+1}+x_{final}\times(-2)^i \end{align*}$
因此，进位为 $- 1$ ，本位为 $x_{final}=x - 2$ （在 $0$ 到 $1$ 的范围内）
若 $x = - 1$ ，同理， $x\times(-2)^i=(-1)\times(-2)^i=((1) + (-2))\times(-2)^i=(-2)^{i+1}+(-2)^i$ ，所以进位为 $1$ ，本位为 $1$
若 $x = 0$ 或 $x = 1$ ，则不必考虑进位（ $c = 0$ ）

完毕。

时间复杂度 $\mathcal O(N^2)$
空间复杂度 $\mathcal O(N\log N)$

AC代码

C++

class Solution {
public:vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {vector<int> ans;for (int i = arr1.size() - 1, j = arr2.size() - 1, c = 0; i >= 0 || j >= 0 || c; i--, j--) {int a = i >= 0 ? arr1[i] : 0;int b = j >= 0 ? arr2[j] : 0;int x = a + b + c;if (x >= 2) {x -= 2;c = -1;}else if (x == -1) {x = 1;c = 1;}else {c = 0;}ans.push_back(x);}while (ans.size() > 1 && !ans.back()) {ans.pop_back();}reverse(ans.begin(), ans.end());return ans;}
};

Python

# from typing import Listclass Solution:def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:i, j, c = len(arr1) - 1, len(arr2) - 1, 0ans = []while i >= 0 or j >= 0 or c:a = arr1[i] if i >= 0 else 0b = arr2[j] if j >= 0 else 0x = a + b + cif x >= 2:x -= 2c = -1elif x == -1:x = 1c = 1else:c = 0ans.append(x)i, j = i - 1, j - 1while len(ans) > 1 and not ans[-1]:ans.pop()ans.reverse()return ans