Convert to Base -2

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".

Examples

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 <= 10^9

Solution

Method 1 – Repeated Division and Remainder 1

Intuition

To convert a number to base -2, we repeatedly divide the number by -2 and record the remainders. Since the base is negative, we need to ensure the remainder is always non-negative (0 or 1 for binary). If the remainder is negative, we adjust both the quotient and remainder accordingly.

Approach

1. If n is 0, return "0".
2. While n is not 0:
   • Compute remainder r = n % -2. If r < 0, set r += 2 and n += 1.
   • Append r to the answer string (as a digit).
   • Update n = n // -2.
3. Reverse the answer string and return it.

Code

C++

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0) return "0";
        string ans;
        while (n != 0) {
            int r = n % -2;
            n /= -2;
            if (r < 0) {
                r += 2;
                n += 1;
            }
            ans.push_back(r + '0');
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Go

func baseNeg2(n int) string {
    if n == 0 {
        return "0"
    }
    ans := []byte{}
    for n != 0 {
        r := n % -2
        n /= -2
        if r < 0 {
            r += 2
            n += 1
        }
        ans = append(ans, byte(r)+'0')
    }
    // reverse
    for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
        ans[i], ans[j] = ans[j], ans[i]
    }
    return string(ans)
}

Java

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

Kotlin

class Solution {
    fun baseNeg2(n: Int): String {
        if (n == 0) return "0"
        var x = n
        val ans = StringBuilder()
        while (x != 0) {
            var r = x % -2
            x /= -2
            if (r < 0) {
                r += 2
                x += 1
            }
            ans.append(r)
        }
        return ans.reverse().toString()
    }
}

Python

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"
        ans = []
        while n != 0:
            r = n % -2
            n //= -2
            if r < 0:
                r += 2
                n += 1
            ans.append(str(r))
        return ''.join(ans[::-1])

Rust

impl Solution {
    pub fn base_neg2(mut n: i32) -> String {
        if n == 0 {
            return "0".to_string();
        }
        let mut ans = Vec::new();
        while n != 0 {
            let mut r = n % -2;
            n /= -2;
            if r < 0 {
                r += 2;
                n += 1;
            }
            ans.push((r as u8 + b'0') as char);
        }
        ans.iter().rev().collect()
    }
}

TypeScript

class Solution {
    baseNeg2(n: number): string {
        if (n === 0) return "0";
        let ans = '';
        while (n !== 0) {
            let r = n % -2;
            n = Math.floor(n / -2);
            if (r < 0) {
                r += 2;
                n += 1;
            }
            ans = r.toString() + ans;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(log n), since the number of digits in base -2 is proportional to the number of divisions.
• 🧺 Space complexity: O(log n), for storing the result string.