Abstract / Summary

Add two numbers given in base negative two and return the result in the same format.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The addNegabinary method receives two arrays that represent numbers in base -2 (negabinary) and returns a new array that encodes the sum, also in base -2. The implementation follows a three-phase approach: it first translates each input array into a Python integer, adds the two integers, and finally converts the resulting integer back into a negabinary representation. Python’s native support for arbitrarily large integers allows the algorithm to work without overflow concerns.

Key Steps

Conversion from negabinary to decimal

The inner function decimal walks the input list from the least-significant digit to the most-significant digit, accumulating the value by repeatedly multiplying a running power of -2.

def decimal(arr):
    value = 0
    power = 1          # (-2) ** 0
    for a in reversed(arr):
        if a == 1:
            value += power
        power *= -2
    return value

The use of reversed avoids the need to compute indices, and the multiplication power *= -2 updates the positional weight in constant time per digit.

Decimal addition

After both arrays have been converted, the two integer values are summed directly.

value = decimal(arr1) + decimal(arr2)

Because the conversion yields ordinary Python integers, the addition leverages the highly optimized C implementation of integer arithmetic in the interpreter.

Edge-case handling for a zero result

If the sum is exactly zero, the algorithm returns a single-element list containing 0. This special case prevents the later loop from producing an empty list, which would be an invalid representation of zero in negabinary.

if value == 0:
    return [0]

Conversion from decimal back to negabinary

The conversion back to base -2 uses a loop that repeatedly applies divmod with a divisor of -2. The divmod call returns both the quotient and the remainder in a single operation, which is more efficient than performing division and modulus separately.

result = []
while value != 0:
    value, remainder = divmod(value, -2)
    if remainder == -1:
        value += 1
        result.append(1)
    else:
        result.append(remainder)

When the remainder is -1, the algorithm adjusts the quotient by adding one and records a digit of 1. This correction implements the carry logic required for negative bases, ensuring that each digit in the final list is either 0 or 1.

The final step reverses the collected digits to present them in most-significant-to-least-significant order, matching the input format.

return reversed(result)

Edge Cases Handled

The code explicitly addresses two important edge conditions. The first is the situation where the sum of the two numbers equals zero; the early return of [0] guarantees a correct representation. The second is the occurrence of a -1 remainder during the back-conversion loop. By incrementing the quotient and appending 1, the algorithm correctly normalizes the digit to the allowed range for negabinary (0 or 1) while preserving the overall value.

Performance Optimizations

The implementation benefits from several low-level efficiencies. The conversion from negabinary to decimal updates the positional weight with a single multiplication per digit, avoiding exponentiation or repeated power calculations. The use of divmod in the reverse conversion combines division and remainder extraction into one operation, reducing interpreter overhead. Additionally, Python’s built-in arbitrary-precision integer type handles large intermediate values without extra bookkeeping, allowing the algorithm to remain concise while still operating at near-native speed for the arithmetic involved.

Imagine that these lists of numbers are like special secret messages written in a code where the number negative two is the boss. To figure out what the secret message says, the computer treats each number like a piece of a puzzle.

First, the computer looks at the lists and turns them into a normal number that is easy to understand. It starts from the end of the list and multiplies by negative two over and over again to build the total value. Once the computer has the total from both lists, it adds them together just like adding toys in a pile.

Now that the computer has the combined total, it has to turn that big number back into the secret code. It does this by using a special shrinking trick where it divides the number by negative two repeatedly. Every time there is a little piece left over, that piece becomes a digit in the new secret code. If the division ends up with a grumpy negative number, the computer fixes it by adding a one to the next step so the message stays perfect. Finally, the computer gathers all those little pieces it found and flips them around to show the final secret list.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	Go	C#	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	Garvit244		Python
	halfrost					Go
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM						C#
	varunu28				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality