LC 1073. Adding Two Negabinary Numbers

https://leetcode.com/problems/adding-two-negabinary-numbers/

观察得到两条重要规则：

  1. 进位规则

    • ith上的value(假设value >= 2), 可以转换为 (i+1)th的value//2 以及(i+2)th的value // 2
    • 2 * (-2)^(2n+1) 可以分解成为 (-2)^(2n+3) - (-2)^(2n+2).
    • 2 * (-2)^(2n) 可以分解成为 (-2)^(2n+2) - (-2)^(2n+1).
  2. 结束规则：
    • 对高两位 ith 和 i+1th 上的值分别是 x, y
    • 如果 2*x == y 那么就可以终止
    • 如果没有这点可以一直循环往上加
class Solution:
    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        st = []
        a, b = 0, 0

        n = max(len(arr1), len(arr2))
        for i in range(n):
            x = 0
            if i < len(arr1):
                x += arr1[len(arr1) - 1 - i]
            if i < len(arr2):
                x += arr2[len(arr2) - 1 - i]

            a += x
            st.append(a % 2)
            a, b = b + a // 2, a // 2

        while a != 2 * b:
            st.append(a % 2)
            a, b = b + a // 2, a // 2

        while st and st[-1] == 0:
            st.pop()

        if not st:
            return [0]
        ans = st[::-1]
        return ans