Problem Description

Given an integer n, convert it to its representation in base -2 and return it as a string. The base -2 representation uses digits 0 and 1, but the base is negative two, so the place values alternate in sign: 1, -2, 4, -8, 16, and so on.

The returned string should not contain any leading zeros unless the number is zero itself.
Constraints:

• 0 <= n <= 10^9

Thought Process

The challenge is to convert a decimal number into a negative base, which is not common. In positive base conversions, we repeatedly divide by the base and collect remainders. For base -2, the negative base means the remainders and quotients behave differently, sometimes resulting in negative remainders or quotients.

A naive approach might be to simulate normal base conversion, but negative bases require careful handling to ensure all digits are 0 or 1 and the result is valid. The main trick is adjusting the quotient and remainder when the remainder is negative.

The process involves thinking in terms of how "borrowing" works in negative bases, and how to always get a non-negative remainder at each step.

Solution Approach

Here's how to convert an integer n to its base -2 representation:

1. Loop until n becomes zero:
   • At each step, compute the remainder r = n % -2.
   • If r is negative, adjust it by adding the base (i.e., r += 2) and also adjust n by increasing it by 1 (since you "borrowed" a -2).
   • Append r to the result (which will always be 0 or 1).
   • Update n = n // -2 (using integer division).
2. Edge Case: If n is zero, return "0".
3. Reverse the result: Since the digits are computed from least significant to most significant, reverse them at the end.

This approach ensures all digits are 0 or 1, and the representation is correct for negative bases. The adjustment step is crucial for keeping remainders non-negative.

Example Walkthrough

Let's convert n = 6 to base -2.

• Step 1:
  • n = 6
  • 6 % -2 = 0
  • Append 0
  • n = 6 // -2 = -3
• Step 2:
  • n = -3
  • -3 % -2 = -1 (negative!)
  • Adjust: r = -1 + 2 = 1
  • n = (-3 // -2) + 1 = 1 + 1 = 2
  • Append 1
• Step 3:
  • n = 2
  • 2 % -2 = 0
  • Append 0
  • n = 2 // -2 = -1
• Step 4:
  • n = -1
  • -1 % -2 = -1
  • Adjust: r = -1 + 2 = 1
  • n = (-1 // -2) + 1 = 0 + 1 = 1
  • Append 1
• Step 5:
  • n = 1
  • 1 % -2 = -1
  • Adjust: r = -1 + 2 = 1
  • n = (1 // -2) + 1 = -1 + 1 = 0
  • Append 1
• Result:
  • Digits collected (in reverse): 0 1 0 1 1
  • Reverse: "11010"

So, 6 in base -2 is "11010".

Time and Space Complexity

Brute-force approach: There is no meaningful brute-force here, since direct simulation is the only way.

Optimized approach (as above):

• Time Complexity: O(log n) — Each loop divides n by -2, so the number of iterations is proportional to the number of digits in base -2, which is O(log n).
• Space Complexity: O(log n) — We store the resulting digits, which is at most O(log n) in length.

Summary

Converting to base -2 requires careful handling of negative bases, especially when the remainder is negative. By adjusting the remainder and quotient as needed, we ensure all digits are 0 or 1 and the representation is valid. The process is efficient, with both time and space complexity proportional to the number of digits in the result. This solution elegantly extends the classic base conversion algorithm to negative bases.

Code Implementation

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"
        res = []
        while n != 0:
            n, rem = divmod(n, -2)
            if rem < 0:
                n += 1
                rem += 2
            res.append(str(rem))
        return ''.join(reversed(res))
      

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0) return "0";
        string res = "";
        while (n != 0) {
            int rem = n % -2;
            n /= -2;
            if (rem < 0) {
                rem += 2;
                n += 1;
            }
            res = to_string(rem) + res;
        }
        return res;
    }
};
      

class Solution {
    public String baseNeg2(int n) {
        if (n == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (n != 0) {
            int rem = n % -2;
            n /= -2;
            if (rem < 0) {
                rem += 2;
                n += 1;
            }
            sb.append(rem);
        }
        return sb.reverse().toString();
    }
}
      

var baseNeg2 = function(n) {
    if (n === 0) return "0";
    let res = [];
    while (n !== 0) {
        let rem = n % -2;
        n = Math.floor(n / -2);
        if (rem < 0) {
            rem += 2;
            n += 1;
        }
        res.push(rem);
    }
    return res.reverse().join('');
};