LeetCode 1017 - Convert to Base -2

LeetCode Problem 1017

Difficulty: 🟡 Medium
Topics: Math

Solution

Problem Understanding

This problem asks us to convert a non-negative integer n into its representation using base -2, instead of the usual positive bases such as base 2, base 10, or base 16.

In standard binary representation, numbers are written as powers of 2. For example:

$$13 = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$$

which becomes "1101".

In this problem, however, the base is negative, specifically -2. That means each position represents a power of -2:

$$(-2)^0 = 1,\quad (-2)^1 = -2,\quad (-2)^2 = 4,\quad (-2)^3 = -8$$

and so on.

For example:

$$2 = (-2)^2 + (-2)^1$$

because:

$$4 + (-2) = 2$$

So the answer is "110".

The input consists of a single integer n, where:

$$0 \leq n \leq 10^9$$

The output must be a binary string representing n in base -2, using only the digits '0' and '1'.

The problem explicitly states that the returned string must not contain leading zeros, unless the result itself is "0".

The constraint n <= 10^9 tells us that the input size is not extremely large, but we still need an efficient mathematical approach. Since binary-like representations grow logarithmically with respect to the number size, we should aim for an O(log n) solution.

Several edge cases deserve attention upfront. The most important one is n = 0, because repeated division would otherwise produce an empty result, but the required output is "0". Another subtle issue comes from the fact that the base is negative. In ordinary base conversion, repeated division naturally produces non-negative remainders. With a negative base, division can produce negative remainders, which would violate the binary digit requirement of only 0 and 1. We must carefully adjust the quotient and remainder to ensure valid digits.

Approaches

Brute Force Approach

A brute force solution would attempt to generate possible binary strings and check which one evaluates to n in base -2.

For example, we could enumerate strings like:

• "0"
• "1"
• "10"
• "11"
• "100"

and evaluate their decimal value using:

$$\sum digit_i \times (-2)^i$$

until we find the correct representation.

This works because every valid base -2 representation uniquely corresponds to a decimal number.

However, this approach becomes impractical very quickly. The number of candidate binary strings grows exponentially with the string length. Since n can be as large as 10^9, the representation may require dozens of bits, making exhaustive search far too expensive.

The brute force approach is therefore computationally infeasible.

Optimal Approach, Repeated Division by -2

The key observation is that base conversion still works using repeated division, even with a negative base.

In ordinary base conversion:

• Divide by the base
• Record the remainder
• Continue with the quotient

For example, converting to base 2 repeatedly divides by 2.

We can apply the same principle here using base -2.

At each step:

$$n = (-2) \times quotient + remainder$$

The remainder must always be either 0 or 1, because we are building a binary representation.

The challenge is that dividing by a negative number can produce a negative remainder. For example:

$$1 \div (-2)$$

may lead to an invalid remainder such as -1.

To fix this, whenever the remainder becomes negative, we adjust it:

• Add 2 to the remainder
• Add 1 to the quotient

This preserves the equation while ensuring the remainder stays in {0, 1}.

Since every division roughly halves the magnitude of the number, the algorithm runs in logarithmic time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^k × k)	O(k)	Enumerates possible binary strings and evaluates each one
Optimal	O(log n)	O(log n)	Repeated division by -2 with remainder adjustment

Here, k is the number of digits in the base -2 representation.

Algorithm Walkthrough

1. Handle the special case where n == 0.

Since repeated division would produce no digits, directly return "0". 2. Create a list to store digits.

We build digits from least significant to most significant, exactly like ordinary base conversion. A list allows efficient appending. 3. Repeat while n != 0.

Each iteration extracts one digit of the base -2 representation. 4. Compute quotient and remainder.

Use:

quotient = n // -2
remainder = n % -2

Since Python and mathematical division with negative numbers may produce a negative remainder, this remainder is not always valid. 5. Fix negative remainders.

If remainder < 0:

• Add 2 to the remainder
• Add 1 to the quotient

This guarantees the remainder becomes either 0 or 1. 6. Append the digit.

Convert the remainder into a string and store it. 7. Update n.

Set:

n = quotient

Continue processing the remaining higher-order digits. 8. Reverse the collected digits.

Since digits are generated from least significant to most significant, reverse them before joining into the final string.

Why it works

The algorithm maintains the invariant:

$$n = (-2) \times quotient + remainder$$

at every iteration, where the remainder is always either 0 or 1.

Each iteration extracts exactly one valid base -2 digit while reducing the magnitude of n, guaranteeing eventual termination. Because every remainder corresponds to a valid binary digit and the representation is constructed from least significant to most significant, reversing the digits produces the correct base -2 representation.

Python Solution

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"

        digits: list[str] = []

        while n != 0:
            quotient = n // -2
            remainder = n % -2

            if remainder < 0:
                remainder += 2
                quotient += 1

            digits.append(str(remainder))
            n = quotient

        return "".join(reversed(digits))

The implementation begins by handling the special case n == 0, since zero must return "0" directly.

We then create a list called digits to store the generated binary digits. During each iteration, we divide n by -2 and compute the remainder.

Because negative division may produce an invalid negative remainder, we check whether remainder < 0. If it is, we shift the remainder into the valid range {0, 1} by adding 2, and compensate by increasing the quotient by 1.

Each valid remainder becomes one digit of the answer, appended to the list. Since the least significant digit is generated first, we reverse the list before joining everything into the final string.

This implementation directly mirrors the mathematical definition of base conversion while carefully accounting for the negative base.

Go Solution

func baseNeg2(n int) string {
	if n == 0 {
		return "0"
	}

	digits := []byte{}

	for n != 0 {
		quotient := n / -2
		remainder := n % -2

		if remainder < 0 {
			remainder += 2
			quotient++
		}

		digits = append(digits, byte(remainder)+'0')
		n = quotient
	}

	// Reverse digits
	left, right := 0, len(digits)-1
	for left < right {
		digits[left], digits[right] = digits[right], digits[left]
		left++
		right--
	}

	return string(digits)
}

The Go implementation follows the same logic as the Python version, but there are a few language-specific differences.

Instead of storing strings, we use a []byte slice to efficiently build characters. Each remainder is converted into a character by adding '0'.

Since Go does not provide a built-in reverse operation for slices, we reverse the byte slice manually using a two-pointer swap approach.

Integer overflow is not a concern here because the problem constraint is only up to 10^9, well within Go's int range.

Worked Examples

Example 1: n = 2

We repeatedly divide by -2.

Step	Current n	Quotient	Remainder	Adjusted?	Digits
1	2	-1	0	No	["0"]
2	-1	0	-1	Yes → (1,1)	["0","1"]
3	1	-1	-1	Yes → (0,1)	["0","1","1"]

Reversing:

"110"

Verification:

$$1 \times (-2)^2 + 1 \times (-2)^1 + 0$$

$$4 - 2 = 2$$

Example 2: n = 3

Step	Current n	Quotient	Remainder	Adjusted?	Digits
1	3	-2	-1	Yes → (-1,1)	["1"]
2	-1	0	-1	Yes → (1,1)	["1","1"]
3	1	-1	-1	Yes → (0,1)	["1","1","1"]

Reversing:

"111"

Verification:

$$4 - 2 + 1 = 3$$

Example 3: n = 4

Step	Current n	Quotient	Remainder	Adjusted?	Digits
1	4	-2	0	No	["0"]
2	-2	1	0	No	["0","0"]
3	1	-1	-1	Yes → (0,1)	["0","0","1"]

Reversing:

"100"

Verification:

$$1 \times (-2)^2 = 4$$

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each iteration divides the number by -2, reducing its magnitude
Space	O(log n)	The output string and digit list store logarithmically many digits

The number shrinks approximately by a factor of 2 at every step, so the loop runs proportional to the number of digits in the base -2 representation. Since the representation length is logarithmic in n, both time and auxiliary storage are O(log n).

Test Cases

solution = Solution()

assert solution.baseNeg2(2) == "110"      # Example case
assert solution.baseNeg2(3) == "111"      # Example case
assert solution.baseNeg2(4) == "100"      # Example case

assert solution.baseNeg2(0) == "0"        # Smallest possible input
assert solution.baseNeg2(1) == "1"        # Single digit result
assert solution.baseNeg2(5) == "101"      # Alternating signs
assert solution.baseNeg2(6) == "11010"    # Multi-step conversion
assert solution.baseNeg2(7) == "11011"    # Consecutive number
assert solution.baseNeg2(8) == "11000"    # Power-related case

assert solution.baseNeg2(100) == "110100100"   # Larger input
assert solution.baseNeg2(1_000_000_000)        # Upper constraint stress test

Test	Why
n = 2	Verifies the first example
n = 3	Verifies repeated remainder adjustment
n = 4	Verifies power of -2
n = 0	Validates special-case handling
n = 1	Tests smallest positive number
n = 5	Checks alternating sign behavior
n = 6	Tests multiple quotient adjustments
n = 7	Verifies nearby consecutive values
n = 8	Tests larger power-related structure
n = 100	Confirms correctness for medium input
n = 10^9	Stress tests upper constraint

Edge Cases

Case 1: n = 0

Zero is the most important edge case because repeated division would never execute, leaving us with an empty digit list. Returning an empty string would be incorrect, since the problem explicitly requires "0".

The implementation handles this immediately with:

if n == 0:
    return "0"

This guarantees correctness before entering the main loop.

Case 2: Negative remainder during division

Unlike normal base conversion, dividing by a negative base can produce negative remainders. For example:

$$1 % (-2) = -1$$

A negative remainder would violate the binary digit requirement of only 0 and 1.

The implementation fixes this by adjusting:

if remainder < 0:
    remainder += 2
    quotient += 1

This preserves the mathematical equality while ensuring valid digits.

Case 3: Leading zeros

It is easy to accidentally generate leading zeros if the algorithm appends extra digits or mishandles the termination condition.

Since the loop stops exactly when n == 0, no unnecessary high-order digits are added. Reversing the collected digits naturally produces a representation without leading zeros, except for the special case "0" handled separately.