LeetCode 1017: Convert to Base -2

Problem Restatement

We are given a non-negative integer n.

We need to return its representation in base -2 as a string (without leading zeros unless the answer is "0").

In base -2, each digit is 0 or 1, and the place values are (-2)^0 = 1, (-2)^1 = -2, (-2)^2 = 4, (-2)^3 = -8, and so on.

The official constraints state that 0 <= n <= 10^9.

Input and Output

Function shape:

def baseNeg2(n: int) -> str:
    ...

Examples

Example 1:

n = 2

2 = (-2)^2 + (-2)^1 + 0 = 4 - 2 = 2. So representation is "110".

Wait: (-2)^2 = 4, (-2)^1 = -2. So 110 means 1*4 + 1*(-2) + 0 = 2. ✓

Answer:

"110"

Example 2:

n = 3

3 = 4 + (-2) + 1 = (-2)^2 + (-2)^1 + (-2)^0. So "111".

Answer:

"111"

Example 3:

n = 4

4 = (-2)^2 = 1 * 4. So "100".

Answer:

"100"

Key Insight

The conversion is similar to standard base conversion, but with base -2.

For each step:

1. digit = n % 2 (always 0 or 1, since we want non-negative remainders).
2. Append digit to the result (built in reverse).
3. n = -(n // 2) because dividing by -2 flips the sign.

Or equivalently:

digit = n & 1
n = -(n >> 1)

The bitwise trick works because n >> 1 is floor division by 2, and then we negate to account for the negative base.

Algorithm

1. If n == 0, return "0".
2. Build the representation bit by bit:
   • digit = n % 2 (or n & 1)
   • n = -(n // 2) (or -(n >> 1))
   • Prepend digit to the result.
3. Continue until n == 0.

Correctness

This is a standard base conversion algorithm adapted for a negative base.

At each step, digit is the least significant bit of the current value in base -2. After extracting it, dividing by the base (and negating) shifts to the next position.

Because the base is -2, after dividing n by 2 (integer division) to remove the least significant place value, we negate to account for the sign change at each power.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

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

        bits = []
        while n != 0:
            bits.append(str(n & 1))
            n = -(n >> 1)

        return "".join(reversed(bits))

Code Explanation

Handle the zero case:

if n == 0:
    return "0"

Extract bits from least significant to most significant:

while n != 0:
    bits.append(str(n & 1))
    n = -(n >> 1)

n & 1 gives the current bit. -(n >> 1) divides by -2.

Reverse the collected bits to get the most-significant-first representation:

return "".join(reversed(bits))

Testing

def run_tests():
    s = Solution()

    assert s.baseNeg2(2) == "110"
    assert s.baseNeg2(3) == "111"
    assert s.baseNeg2(4) == "100"
    assert s.baseNeg2(0) == "0"
    assert s.baseNeg2(1) == "1"

    print("all tests passed")

run_tests()