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

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground: