Convert to Base -2
MedPrompt
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 = 2Example 2:
Input: n = 3
Output: "111"
Explantion: (-2)2 + (-2)1 + (-2)0 = 3Example 3:
Input: n = 4
Output: "100"
Explantion: (-2)2 = 4
Constraints:
0 <= n <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach adapts the standard algorithm for converting a number to a positive base. It repeatedly takes the number modulo -2 to find the last digit and then divides the number by -2 to process the rest. A special correction is needed because the remainder of a division by -2 can be negative in some programming languages.
Algorithm
1. Handle the base case where n = 0, returning "0".2. Create a StringBuilder to build the result string.3. Loop as long as n is not equal to 0.4. Inside the loop, calculate the remainder: remainder = n % -2.5. Update n by integer division: n = n / -2.6. If the remainder is negative, adjust it by adding 2 (remainder += 2) and adjust the quotient by adding 1 (n += 1).7. Append the adjusted remainder to the StringBuilder.8. After the loop, reverse the StringBuilder and convert it to a string.9. Return the final string.
Walkthrough
The core idea is that any integer n can be uniquely represented as n = q * (-2) + r, where the remainder r is either 0 or 1. These remainders, when collected, form the digits of the base -2 representation.
We can implement this iteratively. In a loop, we calculate the remainder and the new quotient.
The standard integer division n / (-2) and modulo n % (-2) in languages like Java or C++ can produce a negative remainder. For example, -1 % -2 is -1.
Our digits must be 0 or 1. If we get a remainder r = -1, we need to adjust. The equation n = q * (-2) - 1 can be rewritten as n = (q + 1) * (-2) + 2 - 1 = (q + 1) * (-2) + 1.
This means if the remainder is -1, the digit is 1, and we must add 1 to the quotient q for the next iteration.
class Solution { public String baseNeg2(int n) { if (n == 0) { return "0"; } StringBuilder sb = new StringBuilder(); while (n != 0) { int remainder = n % -2; n /= -2; if (remainder < 0) { remainder += 2; n += 1; } sb.append(remainder); } return sb.reverse().toString(); }}Complexity
Time
O(log n). The value of `n` is approximately halved in each iteration, so the number of iterations is logarithmic with respect to `n`. String operations inside the loop take amortized constant time, and the final reversal takes `O(log n)`.
Space
O(log n). The space is required to store the digits of the result in the StringBuilder. The length of the result is proportional to `log n`.
Trade-offs
Pros
It's a direct adaptation of the familiar base conversion algorithm.
The logic is relatively straightforward to understand if one is familiar with how integer division and modulo work with negative numbers.
Cons
The need for correction logic for negative remainders makes the code slightly more complex and potentially error-prone.
It might be slightly less performant due to the conditional check and extra arithmetic operations in some iterations.
Solutions
Solution
public class Solution { public string BaseNeg2(int n) { if (n == 0) { return "0"; } int k = 1; StringBuilder ans = new StringBuilder(); int num = n; while (num != 0) { if (num % 2 != 0) { ans.Append('1'); num -= k; } else { ans.Append('0'); } k *= -1; num /= 2; } char[] cs = ans.ToString().ToCharArray(); Array.Reverse(cs); return new string(cs); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.