# Convert to Base -2
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/convert-to-base-2)
Canonical: https://scaleengineer.com/dsa/problems/convert-to-base-2
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb)
---
## Problem
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 <= 109`

# Approaches
## Iterative Division with Remainder Correction
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.
**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`.
**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.
### Explanation
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.

```java
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();
    }
}
```
### 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.`

## Optimized Iteration with Bitwise Operations
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.
**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)`.
**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.
### Explanation
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 `n` is even, `n = 2k`. We can write `n = (-k) * (-2) + 0`. So, `r=0` and `q = -k = n / (-2)`.
- If `n` is odd, `n = 2k + 1`. We can write `n = (-k) * (-2) + 1`. So, `r=1` and `q = -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.

```java
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();
    }
}
```
### 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.`

# Solutions
### CSharp

```csharp
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);
    }
}
```

### Java

```java
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();
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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'

```