Watch 10 video solutions for Convert to Base -2, a medium level problem involving Math. This walkthrough by The Coding Sloth has 2,570 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |