Skip to main content
Talentd

Convert to Base -2 - Solution & Explanation

MediumMath9 min readAsked at: Boeing, Airbnb, Google +1
Practice this problem

Problem Statement

Given an integer n, return a binary string representing its representation in base -2.

Note that the returned string should not have leading zeros unless the string is "0".

 

Example 1:

Input: n = 2
Output: "110"
Explantion: (-2)2 + (-2)1 = 2

Example 2:

Input: n = 3
Output: "111"
Explantion: (-2)2 + (-2)1 + (-2)0 = 3

Example 3:

Input: n = 4
Output: "100"
Explantion: (-2)2 = 4

 

Constraints:

  • 0 <= n <= 109

Approach Overview

Problem Overview: You are given an integer n and need to return its representation in base -2. Unlike normal base conversion, the base is negative, which changes how division and remainders behave while building the digit sequence.

Approach 1: Iterative Division by -2 (O(log n) time, O(log n) space)

The core idea mirrors standard base conversion: repeatedly divide the number by the base and collect remainders. The complication is that dividing by -2 can produce negative remainders. To keep digits valid (0 or 1), you adjust the remainder whenever it becomes negative.

At each step, compute remainder = n % -2. If the remainder is negative, add 2 to it and adjust the quotient using n = (n - remainder) / -2. This ensures every digit is either 0 or 1. Append the remainder to the result and continue until n becomes 0. Since each division roughly halves the magnitude of n, the loop runs about log2(n) times.

This method relies purely on arithmetic properties of negative bases and fits naturally into problems involving math and number theory. The digits are generated from least significant to most significant, so reverse the collected sequence before returning the final string.

Approach 2: Recursive Base -2 Conversion (O(log n) time, O(log n) space)

A recursive formulation follows the same math but expresses the repeated division as a recursive call. Compute the remainder for the current step, normalize it to 0 or 1, then recursively convert the updated quotient (n - remainder) / -2. Each recursive call contributes one digit.

The recursion depth is proportional to the number of digits in the base -2 representation, which is O(log n). While the logic is elegant, recursion adds call stack overhead and is less common in interview solutions compared to the iterative loop.

Recommended for interviews: Iterative division by -2. Interviewers expect you to adapt the standard base-conversion pattern and correctly handle negative remainders. Demonstrating the remainder adjustment shows a clear understanding of how negative bases behave mathematically.

Approach 1: Iterative Division by -2

In this approach, we simulate the traditional base conversion process, but with base -2. For each step, divide the number n by -2, and store the remainder. Update n with the quotient. Make sure to adjust the remainder if it's negative, as this may happen due to the negative base.

The key detail is handling the remainder carefully when it becomes negative, which requires incrementing the quotient.

This Python solution uses a loop that continues until n is reduced to zero. In each iteration, the number n is divided by -2, using divmod to get both the quotient and the remainder. If the remainder is negative, it is adjusted by adding 2, and the quotient is incremented to reflect this adjustment. The remainder is accumulated into the result string from right to left, building the base -2 representation.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(log2n).
Space Complexity: O(log2n) for storing the result string.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Division by -2

Time Complexity: O(log2n).
Space Complexity: O(log2n) for storing the result string.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Division by -2O(log n)O(log n)Best general solution. Efficient and commonly expected in coding interviews.
Recursive Base -2 ConversionO(log n)O(log n)Useful for conceptual clarity or when expressing the conversion process recursively.

Video Solution

Daily Dose of LeetCode: Invert Binary Tree - Python, C++, Java • The Coding Sloth • 2,570 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Convert to Base -2 easy or hard?
Convert to Base -2 is considered a medium difficulty problem. The logic is short but the tricky part is handling negative remainders correctly when dividing by -2, which often confuses candidates unfamiliar with negative base systems.
Convert to Base -2 Python/Java solution
In Python or Java, implement a loop that repeatedly divides n by -2 while storing adjusted remainders (0 or 1). Append digits to a list or string builder and reverse the result at the end. The algorithm runs in O(log n) time and uses O(log n) space.
How to solve Convert to Base -2 in O(log n)?
Use repeated division by -2. At each step compute the remainder n % -2, normalize it to 0 or 1 by adding 2 if it is negative, then update n = (n - remainder) / -2. Continue until n becomes zero and reverse the collected digits.
What is the best approach for Convert to Base -2?
The best approach is iterative division by -2. Repeatedly divide the number by -2, collect the remainder, and adjust it when the remainder becomes negative so that digits remain 0 or 1. This produces the base -2 representation in O(log n) time.
Is Convert to Base -2 asked at Google/Amazon/Meta?
Problems involving unusual base systems and number transformations appear in interviews at companies like Google and Amazon. They test understanding of mathematical reasoning and careful handling of edge cases in arithmetic algorithms.
What data structure is used in Convert to Base -2?
The solution mainly relies on arithmetic operations, but a dynamic string or list is used to store digits as they are generated. Since digits are produced in reverse order, the structure is reversed at the end to build the final result.
What is the time complexity of Convert to Base -2?
The time complexity is O(log n) because each iteration divides the number by 2 in magnitude. The number of digits in the base -2 representation grows logarithmically with respect to n.

Ready to solve this problem?

Practice Convert to Base -2 with our built-in code editor and test cases.

Practice on FleetCode
Previous

Convert Date to Binary

Next

Encode Number