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:
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?