Given an integer n, return a binary string representing its representation in base -2.
Note that the returned string should not have leading zeros unless the string is "0".
Example 1:
Input: n = 2 Output: "110" Explantion: (-2)2 + (-2)1 = 2
Example 2:
Input: n = 3 Output: "111" Explantion: (-2)2 + (-2)1 + (-2)0 = 3
Example 3:
Input: n = 4 Output: "100" Explantion: (-2)2 = 4
Constraints:
0 <= n <= 109Problem Overview: You are given an integer n and need to return its representation in base -2. Unlike normal base conversion, the base is negative, which changes how division and remainders behave while building the digit sequence.
Approach 1: Iterative Division by -2 (O(log n) time, O(log n) space)
The core idea mirrors standard base conversion: repeatedly divide the number by the base and collect remainders. The complication is that dividing by -2 can produce negative remainders. To keep digits valid (0 or 1), you adjust the remainder whenever it becomes negative.
At each step, compute remainder = n % -2. If the remainder is negative, add 2 to it and adjust the quotient using n = (n - remainder) / -2. This ensures every digit is either 0 or 1. Append the remainder to the result and continue until n becomes 0. Since each division roughly halves the magnitude of n, the loop runs about log2(n) times.
This method relies purely on arithmetic properties of negative bases and fits naturally into problems involving math and number theory. The digits are generated from least significant to most significant, so reverse the collected sequence before returning the final string.
Approach 2: Recursive Base -2 Conversion (O(log n) time, O(log n) space)
A recursive formulation follows the same math but expresses the repeated division as a recursive call. Compute the remainder for the current step, normalize it to 0 or 1, then recursively convert the updated quotient (n - remainder) / -2. Each recursive call contributes one digit.
The recursion depth is proportional to the number of digits in the base -2 representation, which is O(log n). While the logic is elegant, recursion adds call stack overhead and is less common in interview solutions compared to the iterative loop.
Recommended for interviews: Iterative division by -2. Interviewers expect you to adapt the standard base-conversion pattern and correctly handle negative remainders. Demonstrating the remainder adjustment shows a clear understanding of how negative bases behave mathematically.
In this approach, we simulate the traditional base conversion process, but with base -2. For each step, divide the number n by -2, and store the remainder. Update n with the quotient. Make sure to adjust the remainder if it's negative, as this may happen due to the negative base.
The key detail is handling the remainder carefully when it becomes negative, which requires incrementing the quotient.
This Python solution uses a loop that continues until n is reduced to zero. In each iteration, the number n is divided by -2, using divmod to get both the quotient and the remainder. If the remainder is negative, it is adjusted by adding 2, and the quotient is incremented to reflect this adjustment. The remainder is accumulated into the result string from right to left, building the base -2 representation.
Time Complexity: O(log2n).
Space Complexity: O(log2n) for storing the result string.
| Approach | Complexity |
|---|---|
| Iterative Division by -2 | Time Complexity: O(log2n). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Division by -2 | O(log n) | O(log n) | Best general solution. Efficient and commonly expected in coding interviews. |
| Recursive Base -2 Conversion | O(log n) | O(log n) | Useful for conceptual clarity or when expressing the conversion process recursively. |
Daily Dose of LeetCode: Invert Binary Tree - Python, C++, Java • The Coding Sloth • 2,570 views views
Watch 9 more video solutions →Practice Convert to Base -2 with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor