You are given two numbers represented in negabinary (base $-2$). Each number is provided as an array of $0$s and $1$s, ordered from the most significant bit to the least significant bit. For instance, arr = [1,1,0,1] corresponds to the value $(-2)^3 + (-2)^2 + (-2)^0 = -3$.

Each input array is guaranteed to contain no leading zeros: either the array is [0], or the first element is $1$.

Given two such arrays arr1 and arr2, compute their sum and return the result in the same negabinary array format, with no leading zeros.

Constraints:

• $1 \leq$ arr1.length, arr2.length $\leq 1000$

• arr1[i] and arr2[i] are $0$ or $1$

• arr1 and arr2 have no leading zeros

The key insight is that adding two negabinary numbers works similarly to adding two regular binary numbers, except the base is $-2$ instead of $2$, which changes how carries propagate. In standard binary addition, a carry of $1$ ...