1017. Convert to Base -2

Given a number N, return a string consisting of "0"s and "1"s that represents its value in base -2 (negative two).

The returned string must have no leading zeroes, unless the string is "0".

Example 1:

Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2

Example 2:

Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

Example 3:

Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4

Note:

  1. 0 <= N <= 10^9

string baseNeg2(int N) {
    string res;
    while (N) {
        cout << "N: " << N << endl;
        res = to_string(N & 1) + res;
        // -x = ~x + 1
        N = -(N >> 1);
    }
    return res.empty() ? "0" : res;
}
string baseNeg2(int N) {
    string res;
    int rem = 0;
    while (N) {
        rem = N % -2;
        N /= -2;
        if (rem < 0) {
            rem -= (-2);
            N += 1;
        }
        res = to_string(rem) + res;
    }
    return res.empty() ? "0" : res;
}

Last updated

Was this helpful?