Problem
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 <= 10^9
Solution (Java)
class Solution {
public String baseNeg2(int n) {
StringBuilder sb = new StringBuilder(Integer.toBinaryString(n));
sb.reverse();
int carry = 0;
int sum;
int pos = 0;
while (pos < sb.length()) {
sum = carry + sb.charAt(pos) - '0';
sb.setCharAt(pos, sum % 2 == 0 ? '0' : '1');
carry = sum / 2;
if (pos % 2 == 1 && sb.charAt(pos) == '1') {
carry += 1;
}
pos++;
if (pos >= sb.length() && carry > 0) {
sb.append(Integer.toBinaryString(carry));
carry = 0;
}
}
return sb.reverse().toString();
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).