Algorithm
Problem Name: 1017. Convert to Base -2
Problem Link: https://leetcode.com/problems/convert-to-base-2/
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
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const baseNeg2 = function(N) {
return negBase(N, -2)
};
function negBase(val, base) {
if(val === 0) return '0'
let result = '';
while (val !== 0) {
let remainder = val % base;
val = Math.trunc(val / base);
if (remainder < 0> {
remainder += -base;
val += 1;
}
result = remainder + result;
}
return result;
}
Input
n = 2
Output
"110"
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def baseNeg2(self, n: int) -> str:
bits = []
while n:
n, rem = divmod(n, -2)
if rem < 0:
n += 1
rem -= -2
bits.append(str(rem))
return "".join(bits[::-1]) if bits else '0'
Input
n = 2
Output
"110"