1017. Convert to Base -2 - Detailed Explanation

Problem Statement

Given an integer n, return a string representing its value in base −2. In base −2, powers of −2 alternate signs: (−2)²=4, (−2)³=−8, etc. The digits of the representation must be 0 or 1, with no leading zeros unless the answer is “0.” citeturn0search0

Examples

Input: n = 2
Output: "110"
Explanation: 110₋₂ = 1·(−2)² + 1·(−2)¹ + 0·(−2)⁰ = 4 − 2 + 0 = 2

Input: n = 3
Output: "111"
Explanation: 111₋₂ = 1·4 + 1·(−2) + 1 = 4 − 2 + 1 = 3

Input: n = 0
Output: "0"

Input: n = −1
Output: "11"
Explanation: 11₋₂ = 1·(−2) + 1 = −2 + 1 = −1

Constraints

• –10⁹ ≤ n ≤ 10⁹

Hints

1. Think of how you convert to a positive base by repeated division and remainder.
2. When dividing by a negative base, the remainder can be negative—adjust the quotient and remainder so the digit is 0 or 1.
3. Stop when the quotient becomes zero, then reverse the collected digits.

Approach – Repeated Division by −2

Explanation

To build the base −2 representation, repeatedly divide n by −2, capturing the remainder as the next digit (0 or 1). Because standard division/remainder may yield a negative remainder, use this rule each step:

1. Compute r = n % (−2).
2. Compute preliminary q = n / (−2) using integer division that rounds toward zero.
3. If r < 0, adjust:
   • r += 2
   • q += 1
4. Append r (0 or 1) to the digits list; set n = q.
5. Repeat until n == 0.
6. If no digits were collected, the number is zero → return "0".
7. Otherwise, reverse the digit list to form the final string.

This ensures at each step the “digit” is nonnegative and less than 2.

Step‑by‑Step Walkthrough for n = −3

1. Start: n = −3.

2. r = (−3) % (−2) = −1, q = (−3) / (−2) = 1 (rounded toward zero). Since r < 0, do r += 2 → r = 1, q += 1 → q = 2. Digits = [1].

3. Now n = 2.

4. r = 2 % (−2) = 0, q = 2 / (−2) = −1. (r≥0) Digits = [1,0].

5. Now n = −1.

6. r = (−1) % (−2) = −1, q = (−1) / (−2) = 0. Adjust: r += 2 → 1, q += 1 → 1. Digits = [1,0,1].

7. Now n = 1.

8. r = 1 % (−2) = 1, q = 1 / (−2) = 0. (r≥0) Digits = [1,0,1,1].

9. n = 0 → stop. Reverse digits → "1101".

10. Check: 1·(−2)³ + 1·(−2)² + 0·(−2)¹ + 1·(−2)⁰ = −8 + 4 + 0 + 1 = −3.

Python Implementation