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

Think of how you convert to a positive base by repeated division and remainder.
When dividing by a negative base, the remainder can be negative—adjust the quotient and remainder so the digit is 0 or 1.
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:

Compute r = n % (−2).
Compute preliminary q = n / (−2) using integer division that rounds toward zero.
If r < 0, adjust:
- r += 2
- q += 1
Append r (0 or 1) to the digits list; set n = q.
Repeat until n == 0.
If no digits were collected, the number is zero → return "0".
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

Start: n = −3.
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].
Now n = 2.
r = 2 % (−2) = 0, q = 2 / (−2) = −1. (r≥0) Digits = [1,0].
Now n = −1.
r = (−1) % (−2) = −1, q = (−1) / (−2) = 0. Adjust: r += 2 → 1, q += 1 → 1. Digits = [1,0,1].
Now n = 1.
r = 1 % (−2) = 1, q = 1 / (−2) = 0. (r≥0) Digits = [1,0,1,1].
n = 0 → stop. Reverse digits → "1101".
Check: 1·(−2)³ + 1·(−2)² + 0·(−2)¹ + 1·(−2)⁰ = −8 + 4 + 0 + 1 = −3.

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Complexity Analysis

Time: O(log |n|) — each division reduces |n| roughly by a factor of 2.
Space: O(log |n|) for the output string and digit buffer.

Common Mistakes

Forgetting to adjust negative remainders, leading to digits outside {0,1}.
Using language’s default integer division that rounds toward −∞ (like Python’s //) without correction.
Not handling the special case n = 0.