Formatted question description: https://leetcode.ca/all/1017.html

# 1017. Convert to Base -2 (Medium)

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

Related Topics:
Math

Similar Questions:

## Solution 1.

For base 2 the bits represent the following numbers

base(2)  = 1 1 1 1
base(10) = 8 4 2 1


For base -2

base(-2) = 1  1  1 1
base(10) = -8 4 -2 1


So if N base 2 only has ones on even-indexed positions, N base -2 should be the same as N base 2.

Example:

5 base 2 = 101
5 base -2 = 101


If N base 2 has ones on odd-indexed positions, then we can get another one to the one-more-significant digit.

This works because 2^i base 2 is the same as 2^(i + 1) base -2 minus 2^i base -2 where i is odd. For example, when i = 1, 2^i base 2 = 2 is the same as 2^(i+1) base -2 = 4 minus 2^i base -2 = -2.

Example:

2 base 2 = 10
2 base -2 = 110 // add one digit at position 2

3 base 2 = 11
3 base -2 = 111 // add one digit at position 2

7 base 2 = 111
7 base -2 = 11011 // add one digit at position 2, we get 211 = 1011; then we add one digit at position 4, we get 11011

// OJ: https://leetcode.com/problems/convert-to-base-2/

// Time: O(logN)
// Space: O(1)
class Solution {
public:
string baseNeg2(int N) {
if (N == 0) return "0";
string ans;
while (N) {
ans += '0' + (N % 2);
N /= 2;
}
int carry = 0;
for (int i = 0; i < ans.size(); ++i) {
ans[i] += carry;
if (ans[i] > '1') {
ans[i] = '0';
carry = 1;
} else carry = 0;
if (ans[i] == '1' && i % 2) carry += 1;
if (carry && i == ans.size() - 1) {
ans += '1';
carry = 0;
}
}
reverse(begin(ans), end(ans));
return ans;
}
};


## Solution 2.

// OJ: https://leetcode.com/problems/convert-to-base-2/

// Time: O(logN)
// Space: O(1)
// Ref: https://leetcode.com/problems/convert-to-base-2/discuss/265507/JavaC%2B%2BPython-2-lines-Exactly-Same-as-Base-2
class Solution {
public:
string baseNeg2(int N) {
if (N == 0) return "0";
string ans;
while (N) {
ans += '0' + (N & 1);
N = -(N >> 1); // divide by -2 and round toward -infinity
}
reverse(begin(ans), end(ans));
return ans;
}
};


Or recursively

// OJ: https://leetcode.com/problems/convert-to-base-2/

// Time: O(logN)
// Space: O(logN)
class Solution {
public:
string baseNeg2(int N) {
return baseNeg2(-(N >> 1)) + to_string(N & 1);
}
};


## Solution 3.

Reference: https://www.geeksforgeeks.org/convert-number-negative-base-representation/

When we get negative r, we add 2 to r and increment N. This works because

r = -1, N = 0
the number is -1

r = 1, N = 1
the number is -2 * 1 - 1 = -1


Example,

N = 3

// first round
r = 3 % -2 = 3 - (3 / -2) * -2 = 3 - (-1 * -2) = 1
N = 3 / -2 = -1

// second round
r = -1 % -2 = -1 - (-1 / -2) * -2 = -1 - (0 * -2) = -1
N = -1 / -2 = 0

// now r is negative, we turn it to be positive
r = -1 + 2 = 1
N = 0 + 1 = 1

// last round
r = 1 % -2 = 1 - (1 / -2) * -2 = 1
N = 1 / -2 = 0

So the result is 111.

// OJ: https://leetcode.com/problems/convert-to-base-2/

// Time: O(logN)
// Space: O(1)
// Ref: https://leetcode.com/problems/convert-to-base-2/discuss/265544/C%2B%2B-Geeks4Geeks
class Solution {
public:
string baseNeg2(int N) {
if (N == 0) return "0";
string ans;
while (N) {
int r = N % -2;
N /= -2;
if (r < 0) {
r += 2;
N++;
}
ans += '0' + r;
}
reverse(begin(ans), end(ans));
return ans;
}
};


Java

class Solution {
public String baseNeg2(int N) {
if (N == 0)
return "0";
int[] bits = new int[32];
int remain = N;
int index = 0;
while (remain > 0) {
bits[index] = remain % 2;
remain /= 2;
index++;
}
for (int i = 0; i <= 31; i++) {
if (i % 2 == 1 && bits[i] == 1)
bits[i + 1]++;
while (bits[i] > 1) {
bits[i] -= 2;
bits[i + 1]++;
}
}
StringBuffer sb = new StringBuffer();
boolean flag = false;
for (int i = 31; i >= 0; i--) {
int bit = bits[i];
if (flag)
sb.append(bit);
else {
if (bit == 1) {
sb.append(bit);
flag = true;
}
}
}
return sb.toString();
}
}