# 1017. Convert to Base -2

## Description

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

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 <= 109

## Solutions

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

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

• class Solution:
def baseNeg2(self, n: int) -> str:
k = 1
ans = []
while n:
if n % 2:
ans.append('1')
n -= k
else:
ans.append('0')
n //= 2
k *= -1
return ''.join(ans[::-1]) or '0'


• func baseNeg2(n int) string {
if n == 0 {
return "0"
}
ans := []byte{}
k := 1
for n != 0 {
if n%2 != 0 {
ans = append(ans, '1')
n -= k
} else {
ans = append(ans, '0')
}
k *= -1
n /= 2
}
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)
}

• function baseNeg2(n: number): string {
if (n === 0) {
return '0';
}
let k = 1;
const ans: string[] = [];
while (n) {
if (n % 2) {
ans.push('1');
n -= k;
} else {
ans.push('0');
}
k *= -1;
n /= 2;
}
return ans.reverse().join('');
}


• public class Solution {
public string BaseNeg2(int n) {
if (n == 0) {
return "0";
}
int k = 1;
StringBuilder ans = new StringBuilder();
int num = n;
while (num != 0) {
if (num % 2 != 0) {
ans.Append('1');
num -= k;
} else {
ans.Append('0');
}
k *= -1;
num /= 2;
}
char[] cs = ans.ToString().ToCharArray();
Array.Reverse(cs);
return new string(cs);
}
}

• impl Solution {
pub fn base_neg2(n: i32) -> String {
if n == 0 {
return "0".to_string();
}
let mut k = 1;
let mut ans = String::new();
let mut num = n;
while num != 0 {
if num % 2 != 0 {
ans.push('1');
num -= k;
} else {
ans.push('0');
}
k *= -1;
num /= 2;
}
ans.chars().rev().collect::<String>()
}
}