Skip to main content
Talentd

Adding Two Negabinary Numbers - Solution & Explanation

MediumArrayMath11 min readAsked at: Grab
Practice this problem

Problem Statement

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.

Example 2:

Input: arr1 = [0], arr2 = [0]
Output: [0]

Example 3:

Input: arr1 = [0], arr2 = [1]
Output: [1]

 

Constraints:

  • 1 <= arr1.length, arr2.length <= 1000
  • arr1[i] and arr2[i] are 0 or 1
  • arr1 and arr2 have no leading zeros

Approach Overview

Problem Overview: You receive two arrays representing integers written in base -2 (negabinary). Each array stores bits from most significant to least significant. Add the two numbers and return the result as another negabinary array without leading zeros.

This problem looks like normal binary addition but the base is -2 instead of 2. That changes how carry propagation works. When the sum of digits exceeds 1 or becomes negative, the carry must be adjusted using the properties of negative bases.

Approach 1: Align and Add with Negabinary Logic (O(n) time, O(1) space)

Treat the arrays like binary numbers and simulate addition from right to left. Use two pointers starting at the last index of each array and maintain a carry. At each step compute total = a + b + carry. The resulting digit becomes total & 1, but the carry is different from standard binary: carry = -(total >> 1). This works because dividing by -2 flips the sign of the carry. Continue until both arrays and the carry are exhausted, then remove leading zeros from the result. This method runs in O(n) time where n is the longer array length and uses O(1) extra space aside from the output buffer. The solution mainly relies on careful carry management while iterating through the array.

Approach 2: Negabinary to Decimal Conversion and Back (O(n) time, O(1) space with big integers)

Another strategy converts both negabinary arrays into decimal values, adds them, and converts the sum back into base -2. Conversion to decimal multiplies each bit by powers of -2. To convert back, repeatedly divide the number by -2 and adjust the remainder so the digit stays 0 or 1. While conceptually simple, this approach relies on large integer arithmetic and careful remainder handling. In languages without arbitrary precision integers, overflow becomes a concern. The runtime is still O(n) because each digit participates in constant-time operations based on math properties of negative bases.

Recommended for interviews: The direct negabinary addition approach is what interviewers expect. It shows you understand how negative-base arithmetic works and can implement custom carry logic. The conversion approach demonstrates conceptual understanding but may be considered less elegant because it relies on big-number conversion rather than operating directly on the bit arrays.

Approach 1: Align and Add with Negabinary Logic

In this approach, we align the input arrays from the least significant bit and implement the addition logic specifically adapted for negabinary numbers. We extend the shorter array with zeros and perform bit addition similar to binary but adjust the carry handling considering the base -2 result.

If the sum at the current position exceeds 1, a negative base affects the carry operation. We iteratively adjust the next two positions as needed to correct the sum, keeping our array free of invalid numbers (>1 or <0).

The provided Python solution reverses both arrays for easy iteration from the least significant bit, balances their lengths with zeros, and then performs addition with adjustment for negabinary carry rules. The result is built by capturing bit sums and managing carry according to negabinary properties, then reversed back before returning.

Code

PythonJavaC++

Python

Java

C++

Complexity

Time Complexity: O(n), where n is the maximum length of the input arrays.

Space Complexity: O(n), due to the storage required for the output array.

Try this approach in the editor →

Approach 2: Negabinary to Decimal Conversion and Back

This approach operates by first converting the input negabinary arrays into decimal integers, performing the arithmetic operation in decimal, and then converting the resultant integer back into a negabinary array. This indirect method leverages built-in arithmetic for addition, and custom helper functions are implemented for conversion between bases.

The Python solution defines functions to transform negabinary arrays to decimal numbers and then back again. For each conversion, operations are conducted differently due to the negative base. Thus, decimalToNegabinary adapts its division remainder logic accordingly.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), primarily due to conversion processes.

Space Complexity: O(n), affected by array storage costs in conversion functions.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Align and Add with Negabinary Logic

Time Complexity: O(n), where n is the maximum length of the input arrays.

Space Complexity: O(n), due to the storage required for the output array.

Negabinary to Decimal Conversion and Back

Time Complexity: O(n), primarily due to conversion processes.

Space Complexity: O(n), affected by array storage costs in conversion functions.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Align and Add with Negabinary LogicO(n)O(1)Best general solution; direct simulation of negabinary addition without conversions
Negabinary to Decimal Conversion and BackO(n)O(1) (excluding big integer storage)Useful for understanding negative base math or when big integer operations are convenient

Video Solution

6 Adding Two Negabinary Numbers || Weekly Contest 139 || Leetcode • code Explainer • 1,636 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Adding Two Negabinary Numbers easy or hard?
Adding Two Negabinary Numbers is considered a Medium difficulty problem. The array traversal itself is simple, but correctly handling carry in base -2 requires understanding negative-base arithmetic, which is the main challenge.
Adding Two Negabinary Numbers Python/Java solution
A typical Python or Java solution iterates from the end of both arrays, computes total = a + b + carry, pushes total & 1 into the result, and updates carry as -(total >> 1). The same logic works across Python, Java, and C++ because it relies only on integer arithmetic and array traversal.
How to solve Adding Two Negabinary Numbers in O(n)?
Traverse both arrays from the least significant bit using two pointers. At each step compute the sum of both bits and the carry. Store total & 1 as the result digit and update carry as -(total >> 1) to account for base -2. Continue until both arrays and the carry are fully processed.
What is the best approach for Adding Two Negabinary Numbers?
The best approach is simulating digit-by-digit addition using negabinary carry rules. Iterate from the end of both arrays, compute the total of the two bits plus carry, store total & 1 as the result bit, and update the carry with -(total >> 1). This runs in O(n) time and O(1) extra space and avoids expensive number conversions.
Is Adding Two Negabinary Numbers asked at Google/Amazon/Meta?
Problems involving unusual number bases and custom carry logic appear in interviews at companies like Google and Meta because they test understanding of number systems and implementation detail. Variations of base conversion and non-standard arithmetic are common in algorithm interviews.
What data structure is used in Adding Two Negabinary Numbers?
The problem primarily uses arrays to represent the binary digits of the negabinary numbers. The algorithm processes these arrays with pointers from right to left while maintaining a carry variable to simulate arithmetic.
What is the time complexity of Adding Two Negabinary Numbers?
The optimal algorithm runs in O(n) time where n is the length of the longer input array. Each digit is processed once during the right-to-left addition. Space complexity is O(1) excluding the output array used to store the resulting negabinary number.

Ready to solve this problem?

Practice Adding Two Negabinary Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays