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.

Description Hints 1 Solution

1017. Convert to Base -2

Medium63.6% acceptance4 companies

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

Example 2:

Input: n = 3
Output: "111"
Explantion: (-2)² + (-2)¹ + (-2)⁰ = 3

Example 3:

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

Constraints:

0 <= n <= 10⁹

Asked at 4 companies

Boeing Airbnb LinkedIn

Google

Topics

Math

Hints open one at a time

Hint 1

Figure out whether you need the ones digit placed or not, then shift by two.

Still stuck?Read 2 approaches.

Open solution