#1017

Medium

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Convert to Base -2

Convert any non-negative integer into its base -2 representation using a math-driven iterative remainder strategy.

Problem Statement

Given a non-negative integer n, return a string representing its value in base -2. The string must not contain leading zeros except when representing zero itself.

For example, given n = 2, the correct output is "110" because (-2)^2 + (-2)^1 = 2. Implement a function that handles numbers up to 10^9 and returns the minimal-length base -2 string.

Examples

Example 1

Input: n = 2

Output: "110" Explantion: (-2)2 + (-2)1 = 2

Example details omitted.

Example 2

Input: n = 3

Output: "111" Explantion: (-2)2 + (-2)1 + (-2)0 = 3

Example details omitted.

Example 3

Input: n = 4

Output: "100" Explantion: (-2)2 = 4

Example details omitted.

Constraints

0 <= n <= 109

Solution Approach

Iterative Division and Remainder

Use repeated division by -2, tracking the remainder each time. If a remainder is negative, adjust by adding 2 and incrementing the quotient. Append the remainder to build the result string from least to most significant digit.

Handle Carryover for Negative Base

Unlike standard binary, dividing by a negative base can produce negative remainders. Always normalize each remainder to 0 or 1 by adjusting the quotient, ensuring that the base -2 digit placement is valid and consistent.

Construct Result String

After processing all divisions, reverse the collected digits to form the final base -2 string. Remove any leading zeros except for the single-digit zero case to meet problem requirements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) because each division reduces n roughly by a factor of 2. Space complexity is O(log n) to store the resulting digits in the output string.

What Interviewers Usually Probe

Are you tracking how negative remainders affect digit placement?
How do you handle normalization of digits when division yields negative remainders?
Can you produce a result string without leading zeros efficiently?

Common Pitfalls or Variants

Common pitfalls

Forgetting to adjust negative remainders leads to incorrect digit sequences.
Appending digits in the wrong order without reversing at the end.
Returning strings with unnecessary leading zeros instead of minimal length.

Follow-up variants

Convert numbers to other negative bases like -3 or -5 using the same remainder adjustment strategy.
Output the base -2 digits as an array of integers instead of a string.
Handle signed integers including negative numbers in base -2 representation.

FAQ

What is the main strategy to solve Convert to Base -2?

Use iterative division by -2, adjust negative remainders to 0 or 1, and construct the final string from least to most significant digit.

Why do negative remainders occur in base -2 conversions?

Dividing by a negative base can yield remainders below zero, which must be normalized to ensure digits are valid binary digits (0 or 1).

Can this method handle large numbers efficiently?

Yes, since each division roughly halves the magnitude of n, the number of steps is proportional to log n, making it efficient up to 10^9.

Do I need to remove leading zeros in the result?

Yes, the output should not have leading zeros except when the number is zero itself, ensuring minimal-length representation.

Is this problem pattern considered math-driven?

Absolutely, the solution relies on careful arithmetic reasoning with negative base properties and remainder normalization.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def baseNeg2(self, n: int) -> str:
        k = 1
        ans = []
        while n:
            if n % 2:
                ans.append('1')
                n -= k
            else:
                ans.append('0')
            n //= 2
            k *= -1
        return ''.join(ans[::-1]) or '0'

Continue Practicing

#1015 smallest integer divisible by k #1012 numbers with repeated digits #1025 divisor game