Convert to Base -2: Negative Base Number Systems

Convert to Base -2 is LeetCode 1017. Given an integer n, return a binary string representing its representation in base -2. The returned string must have no leading zeroes unless the string is "0".

A few examples:

• n = 6 returns "11010" because 1*16 + 1*(-8) + 0*4 + 1*(-2) + 0*1 = 6
• n = 3 returns "111" because 1*4 + 1*(-2) + 1*1 = 3
• n = 0 returns "0"

The twist compared to normal base conversion is that the base is negative. You still divide repeatedly and collect remainders, but a negative base introduces negative remainders that need special handling. The core idea is a small adjustment that keeps every digit in the valid set .

Why this problem matters

Base -2 (also called "negabinary") is a number system where every integer, positive or negative, can be represented using only the digits 0 and 1 with no sign bit. That property makes it a fascinating mathematical curiosity, but the real value for interview preparation is the algorithmic pattern it teaches.

Converting to any base follows the same template: divide by the base, collect the remainder as the next digit, and repeat with the quotient. When the base is negative, the remainder can go negative too. You need a clean way to fix that. The adjustment pattern here, adding the absolute value of the base to the remainder and compensating the quotient, shows up in other problems involving modular arithmetic with negative numbers.

Understanding how Python's floor division and modulo operators interact with negative divisors is also valuable. Many candidates get tripped up by the sign conventions of % and // across different languages. This problem forces you to confront those details head-on.

The key insight

In normal base conversion (say, base 2), you divide n by 2 repeatedly. The remainder is always 0 or 1 because Python's % operator returns a non-negative result when the divisor is positive.

With base -2, the divisor is negative, and Python's % can return a negative remainder. For example, 1 % (-2) gives -1 in Python, and -3 % (-2) gives -1. A digit of -1 is not valid in our system. We need digits to be 0 or 1 only.

The fix: whenever the remainder is negative, add 2 to the remainder (making it 0 or 1) and add 1 to the quotient to compensate. This adjustment preserves the mathematical relationship n = quotient * (-2) + remainder while keeping the remainder non-negative.

Think of it this way: if the remainder is -1, you are saying "I need one less unit at this position." Instead, you can say "I need one more unit at this position (digit = 1) and bump the next higher position by one to compensate."

The solution

def base_neg2(n: int) -> str:
    if n == 0:
        return "0"

    digits = []
    while n != 0:
        remainder = n % (-2)
        n //= -2
        if remainder < 0:
            remainder += 2
            n += 1
        digits.append(str(remainder))

    return "".join(reversed(digits))

The function starts with a special case for zero. Then it loops while n is nonzero, extracting the least significant digit at each step. The remainder becomes the current digit. When the remainder comes back negative, the two-line adjustment fixes it. Digits are collected in reverse order (least significant first), so the final step reverses them into the correct string.

The line n //= -2 does floor division by -2, which moves to the next "place" in the base -2 representation. The line remainder = n % (-2) extracts what belongs in the current place. Together they implement the standard division algorithm, and the if remainder < 0 block is the only addition needed for the negative base.

Visual walkthrough

Here is the algorithm traced step by step on base_neg2(6). Watch how the remainder adjustment triggers on steps where the raw remainder comes back negative.

Notice the pattern: every time n is negative going into a step, the raw remainder from Python's floor division is -1. The adjustment bumps the remainder to 1 and increases the quotient by 1. This always produces a valid digit and a new value of n that eventually reaches 0.

Complexity analysis

Time: Each iteration divides n by -2 (with a possible +1 adjustment). The absolute value of n roughly halves each iteration, though the adjustment can temporarily increase it. In the worst case, the number of digits in the base -2 representation is proportional to log2(n), so the loop runs O(log n) times. Each iteration does constant work.

Space: The digits list stores one character per digit in the output. The base -2 representation of n has O(log n) digits, so the list uses O(log n) space.

The building blocks

1. Division-based base conversion

The core pattern for converting any integer to any base is: divide by the base, collect the remainder, repeat. This same loop appears in problems like converting to base 7, base 16, or computing Excel column titles. The only difference across these problems is the base value and how you map remainders to output characters.

digits = []
while n != 0:
    digits.append(n % base)
    n //= base
result = digits[::-1]

2. Negative remainder adjustment

When working with negative divisors (or negative dividends in some languages), the modulo operation can produce negative remainders. The fix is always the same structure: add the absolute value of the divisor to the remainder and increment the quotient by 1.

if remainder < 0:
    remainder += abs(base)
    n += 1

This preserves the identity n_original = quotient * base + remainder while forcing the remainder into the valid range. You will see this same correction in problems involving cyclic indexing with negative offsets and in modular arithmetic where you need a non-negative result.

Edge cases

• n = 0: The result is "0". The while loop never executes because n is already 0. The special case at the top handles this.
• n = 1: The result is "1". One iteration: 1 % -2 = -1, adjust to remainder=1 and n=0. A single digit "1".
• n = -1: The result is "11". Two iterations produce digits 1 and 1. Verification: 1*(-2) + 1*1 = -2 + 1 = -1.
• Large positive n: The algorithm terminates because dividing by -2 and adjusting always moves toward 0. The output length grows logarithmically.
• Large negative n: Same reasoning applies. Base -2 handles negative numbers naturally without a sign bit, so no separate logic is needed for negative inputs.
• n = 2: The result is "110". Verification: 1*4 + 1*(-2) + 0*1 = 4 - 2 = 2.

From understanding to recall

The algorithm is short, just a while loop with a two-line adjustment. But remembering the exact adjustment (add 2 to the remainder, add 1 to the quotient) and knowing when to apply it (when the remainder is negative) requires practice. The tricky part is not the concept but the specific mechanics of Python's floor division with negative numbers.

There are two building blocks worth drilling separately. First, the standard division-based conversion loop that works for any base. Second, the negative remainder correction. Each takes under a minute to write from scratch. Once both are automatic, you can assemble the full solution quickly and adapt it to any negative base problem.

Related posts

• Reverse Integer - Another problem where careful handling of signs and edge cases in arithmetic is key
• Divide Two Integers - Division-based problem that requires handling negative numbers carefully
• Counting Bits - Binary representation patterns that build intuition for number system conversions

Negative bases are a niche topic, but the underlying skill of modifying a standard algorithm with a small correction is universal. If you want to build that kind of adaptability into your problem-solving toolkit, consistent practice with spaced repetition is the most effective approach. CodeBricks schedules review sessions based on how well you recall each building block, so the patterns that need more work get more attention.