Welcome to Subscribe On Youtube
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:
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) {
if (N == 0 || N == 1) return to_string(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;
}
};
-
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(); } } ############ 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(); } } -
// 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; } }; -
# 1017. Convert to Base -2 # https://leetcode.com/problems/convert-to-base-2/ class Solution: def baseNeg2(self, n: int) -> str: res = [] while n != 0: res.append(n & 1) n = -(n >> 1) return "".join(map(str, res[::-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; let ans: string[] = []; while (n) { if (n % 2) { ans.push('1'); n -= k; } else { ans.push('0'); } k *= -1; n /= 2; } return ans.reverse().join(''); }