Adding Two Negabinary Numbers

Adding Two Negabinary Numbers

What is this problem about?

The Adding Two Negabinary Numbers coding problem is a challenging math-based question. "Negabinary" is a non-standard positional numeral system where the base is $-2$ instead of $2$. You are given two arrays representing negabinary numbers and must return their sum as an array.

Why is this asked in interviews?

This problem is a favorite at Grab because it tests a candidate's ability to adapt a well-known algorithm (binary addition) to a completely different set of rules. It tests mathematical flexibility and the ability to handle unusual "carries" (in negabinary, the carry can be $-1, 0, \text{ or } 1$).

Algorithmic pattern used

This follows the Math Simulation interview pattern. Just like standard binary addition, you work from the least significant bit (end of the array) to the most significant. However, the carry logic is derived from the fact that $(-2)^n + (-2)^n = -2 \times (-2)^n = (-2)^{n+1}$. In negabinary, if the sum at a position is 2, the carry to the next position is actually $-1$.

Example explanation

In base $-2$:

• 1 is $1$
• 110 is $(-2)^2 + (-2)^1 = 4 - 2 = 2$ Adding 1 + 110 (which is $1 + 2 = 3$):

1. Rightmost bit: $1 + 0 = 1$. Carry 0.
2. Next bit: $0 + 1 = 1$. Carry 0.
3. Next bit: $0 + 1 = 1$. Carry 0. Result: 111 ($4 - 2 + 1 = 3$).

Common mistakes candidates make

• Standard Carry Logic: Using a carry of +1 when the sum is 2. In negabinary, $1+1$ at index $i$ results in $0$ at $i$ and $-1$ as a carry for $i+1$.
• Leading Zeros: Returning an array like [0, 0, 1, 1] instead of [1, 1].
• Sign Confusion: Not realizing that even positions have positive weights ($1, 4, 16$) and odd positions have negative weights ($-2, -8, -32$).

Interview preparation tip

When dealing with base $-2$, remember the rule: if the sum $S$ at a position is greater than 1, you can set the current bit to $S-2$ and set the carry to $-1$. If the sum is $-1$, set the current bit to $1$ and the carry to $1$.