Adding Two Negabinary Numbers

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format:  as an array of 0s and 1s, from most significant bit to least significant bit.  For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3.  A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Solution: 

Negabinary numbers are numbers with base -2.
There are three basic rules for negabinary addition (base 10 equivalent in brackets)

• 1 (1) + 1(1) = 110 (2)
• 1 (1) + 1(1) + 1(1) = 111 (3)
• 11 (-1) + 1 (1) = 0 (0)

Let's see a step by step addition of numbers in the example above - 11111 + 101
Step 1:
Adding LSB, 1+1 = 110, we have carry = 11

Step 2:
Adding next LSB + carry

Step 3:
Adding next LSB + carry








Step 4:
Adding next LSB + carry

Step 5:
Adding next LSB + carry

Step 6:
Finally the carry is 11 (-1) + 1 (1) which is equal to 0.

Code :