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 <= 109The key idea in #1017 Convert to Base -2 is understanding how number representation works with a negative base. Instead of the usual base 2 division, we repeatedly divide the number by -2. During each step, we record the remainder which must always be either 0 or 1 to form a valid binary-like representation.
A challenge arises because dividing by a negative base may produce a negative remainder. To fix this, whenever the remainder becomes -1, we adjust it to 1 and increment the quotient accordingly. By continuing this process until the number becomes zero, we build the representation from least significant bit to most significant bit and finally reverse it.
This method is efficient because each division reduces the magnitude of the number, leading to a logarithmic number of steps relative to the input value.
Time Complexity: O(log |n|) since the value shrinks with each division. Space Complexity: O(log |n|) to store the resulting digits.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Repeated Division by -2 with Remainder Adjustment | O(log |n|) | O(log |n|) |
The Coding Sloth
Use these hints if you're stuck. Try solving on your own first.
Figure out whether you need the ones digit placed or not, then shift by two.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of base conversion and negative base representation occasionally appear in coding interviews. The problem tests understanding of number systems, edge cases with division and modulo operations, and careful handling of remainders.
The optimal approach repeatedly divides the number by -2 and records the remainder. If the remainder becomes negative, it is adjusted to 1 and the quotient is incremented. This ensures the resulting digits stay within 0 or 1 while forming the correct base -2 representation.
When dividing by a negative base, the remainder can sometimes become -1. Since valid digits in this representation must be 0 or 1, we convert -1 to 1 and adjust the quotient accordingly. This keeps the representation correct while continuing the conversion process.
The conversion process runs in O(log |n|) time because each division by -2 reduces the magnitude of the number. The number of digits produced is also proportional to the logarithm of the input value.