Problem Description

Given an integer n, you need to convert it to base -2 (negative two) and return the result as a binary string.

In base -2, instead of using powers of 2 (like in regular binary), we use powers of -2. The place values from right to left are:

• Position 0: (-2)^0 = 1
• Position 1: (-2)^1 = -2
• Position 2: (-2)^2 = 4
• Position 3: (-2)^3 = -8
• Position 4: (-2)^4 = 16
• And so on...

For example:

• The number 2 in base -2 is "110" because: 1×4 + 1×(-2) + 0×1 = 4 - 2 + 0 = 2
• The number 3 in base -2 is "111" because: 1×4 + 1×(-2) + 1×1 = 4 - 2 + 1 = 3
• The number 4 in base -2 is "100" because: 1×4 + 0×(-2) + 0×1 = 4

The algorithm works by repeatedly checking if the current number is odd or even:

• If odd, we place a '1' at the current position and adjust the number by subtracting the current power of -2
• If even, we place a '0' at the current position
• Then we divide by 2 and flip the sign of the power (multiply k by -1)

The resulting digits are collected and reversed to get the final answer. If the input is 0, the function returns "0".

The key insight is that we're building the representation digit by digit, handling the alternating positive and negative place values by tracking the current power's sign with variable k.

Intuition

To understand how to convert to base -2, let's first recall how we convert to regular base 2. In base 2, we repeatedly divide by 2 and take remainders. But base -2 is trickier because of the alternating signs.

The key observation is that any number can be expressed as a sum of powers of -2: n = a₀×(-2)⁰ + a₁×(-2)¹ + a₂×(-2)² + a₃×(-2)³ + ...

where each aᵢ is either 0 or 1.

Let's think about what happens when we look at n modulo 2:

• If n is odd, then a₀ must be 1 (since all other terms are even)
• If n is even, then a₀ must be 0

Once we determine a₀, we need to find the remaining digits. If a₀ = 1, we subtract 1 from n (which is the value of (-2)⁰). Now we have: n - a₀ = a₁×(-2)¹ + a₂×(-2)² + a₃×(-2)³ + ...

To find a₁, we can factor out (-2): (n - a₀) = (-2) × (a₁×(-2)⁰ + a₂×(-2)¹ + a₃×(-2)² + ...)

This means: (n - a₀) / (-2) = -a₁ + a₂×(-2)¹ - a₃×(-2)² + ...

But wait, dividing by -2 is the same as dividing by 2 and then negating. However, we want to keep working with positive numbers for simplicity. The clever trick is to track the sign separately using a variable k that alternates between 1 and -1.

When k = 1 (positive position), we subtract k from n if the bit is 1. When k = -1 (negative position), we subtract k from n if the bit is 1 (which actually adds 1 to n).

After determining each bit, we divide by 2 (not -2) and flip the sign of k. This effectively simulates the base -2 conversion while keeping the arithmetic simple.

The process continues until n becomes 0, building up the digits from least significant to most significant, which is why we reverse the result at the end.

Learn more about Math patterns.

Solution Approach

The implementation uses a straightforward iterative approach to build the base -2 representation digit by digit:

1. Initialize variables:

   • k = 1: Tracks the sign of the current power of -2. Starts at 1 for (-2)⁰ = 1
   • ans = []: List to collect the binary digits

2. Main conversion loop (while n:):

   • Check if current bit should be 1: if n % 2:
     • If n is odd, we need a '1' at this position
     • Append '1' to ans
     • Subtract the current power value: n -= k
       • When k = 1, this subtracts 1 (for positive powers)
       • When k = -1, this adds 1 (for negative powers)
   • Otherwise, current bit is 0:
     • Append '0' to ans

3. Prepare for next position:

   • Divide n by 2: n //= 2
   • Flip the sign for the next power: k *= -1
   • This alternates between positive and negative powers as we move to higher positions

4. Build final result:

   • Reverse the collected digits: ans[::-1] (since we built from least to most significant)
   • Join into a string: ''.join(ans[::-1])
   • Handle edge case: Return '0' if the result is empty (when input was 0)

Example walkthrough for n = 6:

• Initially: n = 6, k = 1, ans = []
• Iteration 1: 6 % 2 = 0 → append '0', n = 6 // 2 = 3, k = -1
• Iteration 2: 3 % 2 = 1 → append '1', n = (3 - (-1)) // 2 = 4 // 2 = 2, k = 1
• Iteration 3: 2 % 2 = 0 → append '0', n = 2 // 2 = 1, k = -1
• Iteration 4: 1 % 2 = 1 → append '1', n = (1 - (-1)) // 2 = 2 // 2 = 1, k = 1
• Iteration 5: 1 % 2 = 1 → append '1', n = (1 - 1) // 2 = 0, loop ends
• Result: ans = ['0', '1', '0', '1', '1'] → reversed → "11010"

Verification: 1×16 + 1×(-8) + 0×4 + 1×(-2) + 0×1 = 16 - 8 + 0 - 2 + 0 = 6 ✓

Example Walkthrough

Let's walk through converting n = 3 to base -2:

Initial state: n = 3, k = 1 (sign tracker), ans = [] (digit collector)

Iteration 1: Position 0, power = (-2)⁰ = 1

• Check: 3 % 2 = 1 (odd) → need a '1' at this position
• Append '1' to ans: ans = ['1']
• Adjust n: n = 3 - k = 3 - 1 = 2
• Prepare for next: n = 2 // 2 = 1, k = 1 × (-1) = -1

Iteration 2: Position 1, power = (-2)¹ = -2

• Check: 1 % 2 = 1 (odd) → need a '1' at this position
• Append '1' to ans: ans = ['1', '1']
• Adjust n: n = 1 - k = 1 - (-1) = 2 (subtracting -1 adds 1)
• Prepare for next: n = 2 // 2 = 1, k = -1 × (-1) = 1

Iteration 3: Position 2, power = (-2)² = 4

• Check: 1 % 2 = 1 (odd) → need a '1' at this position
• Append '1' to ans: ans = ['1', '1', '1']
• Adjust n: n = 1 - k = 1 - 1 = 0
• Loop ends since n = 0

Final result:

• Reverse ans: ['1', '1', '1'] → "111"
• Verification: 1×4 + 1×(-2) + 1×1 = 4 - 2 + 1 = 3 ✓

The algorithm cleverly handles the alternating signs by tracking k, which flips between 1 and -1. When we "subtract k" at a negative power position (k = -1), we're actually adding to n, which correctly accounts for the negative contribution of that bit.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm processes the number n by repeatedly dividing it by 2 (through n //= 2) until n becomes 0. This creates a loop that runs approximately log₂(n) times. In each iteration, we perform constant-time operations:

• Checking if n % 2 is true: O(1)
• Appending to the list: O(1) amortized
• Arithmetic operations (n -= k, n //= 2, k *= -1): O(1)

After the loop, we reverse the list and join it, which takes O(log n) time since the list has at most O(log n) elements.

Therefore, the overall time complexity is O(log n) + O(log n) = O(log n).

Space Complexity: O(log n)

The space is used for:

• The ans list which stores the binary digits. In the worst case, this list will have approximately log₂(n) elements since we're essentially converting the number to a base representation.
• The reversed list created during ans[::-1] also takes O(log n) space.
• Other variables (k, n) use O(1) space.

The total space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Negative Adjustments

One of the most common mistakes is misunderstanding how the adjustment n -= k works when dealing with negative powers. When k = -1 (representing a negative power position), subtracting k actually adds 1 to n. This counterintuitive behavior often leads to errors.

Incorrect approach:

if n % 2 == 1:
    result_digits.append('1')
    n -= 1  # Wrong! Always subtracting 1 ignores the sign

Correct approach:

if n % 2 == 1:
    result_digits.append('1')
    n -= power_coefficient  # Correctly handles both positive and negative powers

2. Forgetting to Handle the Zero Case

The algorithm naturally produces an empty list when n = 0, but forgetting to handle this edge case results in returning an empty string instead of "0".

Pitfall:

# Missing edge case handling
return ''.join(reversed(result_digits))  # Returns "" for n=0

Solution:

return ''.join(reversed(result_digits)) if result_digits else '0'

3. Building the Result in Wrong Order

Since we process bits from least significant to most significant, the digits are collected in reverse order. Forgetting to reverse them produces an incorrect result.

Wrong:

return ''.join(result_digits)  # Digits are in reverse order!

Correct:

return ''.join(reversed(result_digits))

4. Integer Division Confusion in Python 2 vs Python 3

In Python 2, / performs integer division for integers, while in Python 3, // is required for integer division. Using / in Python 3 creates float values that break the algorithm.

Problematic in Python 3:

n = n / 2  # Creates a float, causing issues in subsequent iterations

Correct for both Python 2 and 3:

n //= 2  # Integer division works consistently

5. Misunderstanding the Alternating Pattern

Some might try to track the actual power value (1, -2, 4, -8, ...) instead of just the sign coefficient, leading to unnecessary complexity and potential overflow issues with large numbers.

Overcomplicated:

power = 1
while n > 0:
    if n % 2 == 1:
        n -= power
    power *= -2  # Tracking actual power values

Simplified and correct:

k = 1  # Just track the sign
while n > 0:
    if n % 2 == 1:
        n -= k
    k *= -1  # Simply alternate the sign