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.
This approach simplifies the conversion process by using bitwise operations. It leverages the property that the last digit in a base -2 representation is determined by whether the number is even or odd. This avoids the complexity of handling negative remainders from standard modulo operations.
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, determine the last digit (remainder) using bitwise AND: remainder = n & 1.5. Append the remainder to the StringBuilder.6. Update n for the next iteration using a bitwise shift: n = -(n >> 1). This is equivalent to n = (n - remainder) / -2.7. After the loop, reverse the StringBuilder and convert it to a string.8. Return the final string.
Walkthrough
The key insight is that for any number n, the equation n = q * (-2) + r with r \in \{0, 1\} can be solved by looking at the parity of n.
- If
nis even,n = 2k. We can writen = (-k) * (-2) + 0. So,r=0andq = -k = n / (-2). - If
nis odd,n = 2k + 1. We can writen = (-k) * (-2) + 1. So,r=1andq = -k = (n-1)/(-2).
The remainder r is simply n % 2, which can be efficiently calculated using the bitwise AND operation: r = n & 1.
The update for n can be unified: n = (n - r) / (-2).
A more concise and efficient way to write the update for n is n = -(n >> 1). The >> operator is an arithmetic right shift, which preserves the sign and effectively computes the required quotient for the next step, regardless of whether n is positive or negative.
class Solution { public String baseNeg2(int n) { if (n == 0) { return "0"; } StringBuilder res = new StringBuilder(); while (n != 0) { int remainder = n & 1; res.append(remainder); n = -(n >> 1); } return res.reverse().toString(); }}Complexity
Time
O(log n). The number of iterations is logarithmic with respect to `n`. Each iteration involves constant-time bitwise and arithmetic operations.
Space
O(log n). Space is used for the StringBuilder to store the result, which has a length of `O(log n)`.
Trade-offs
Pros
Highly efficient due to the use of fast bitwise operations.
The code is more concise and elegant as it avoids conditional checks for remainder correction.
Less prone to errors related to the nuances of modulo and division with negative numbers.
Cons
The logic behind the n = -(n >> 1) update might be less intuitive to someone not familiar with bitwise manipulations.
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); }}class Solution {public String baseNeg2(int n) { if (n == 0) { return "0"; } int k = 1; StringBuilder ans = new StringBuilder(); while (n != 0) { if (n % 2 != 0) { ans.append(1); n -= k; } else { ans.append(0); } k *= -1; n /= 2; } return ans.reverse().toString(); }}class Solution {public: string baseNeg2(int n) { if (n == 0) { return "0"; } int k = 1; string ans; while (n) { if (n % 2) { ans.push_back('1'); n -= k; } else { ans.push_back('0'); } k *= -1; n /= 2; } reverse(ans.begin(), ans.end()); return ans; }};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'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.