Convert to Base -2 LeetCode Solution

Difficulty Level Medium
Frequently asked in Airbnb Grab LinkedInViews 1905

Problem Statement

Convert to Base -2 LeetCode Solution – 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".

Input: n = 2
Output: "110"
Explantion: (-2)2 + (-2)1 = 2

Explanation

The logic is similar to positive base logic. But the difference is when the remainder is negative.
Why would that matter? Basically, remainders are going to be the digits we use in the output. So we can’t have negative numbers there, right?

So how do we handle it? Eg: For num/base, we have num=base*q+d where d is the remainder and q is the quotient. If d is negative, we can make it positive as follows:
num=base*q-r+(d+r) where base=-r
num=(q+1)*base+(d+r)

base2 function is quite the basis of basis.

check the last digit by N%2 or N&1.
If it’s 1, you get 1.
If it’s 0, you get 0.

shift to right N >> 1.
This actually does two things:
2.1 Minus 1 if last digit is 1.
2.2 Divide N by 2.

base -2 is no difference,
except that we need to divide N by -2.

So we do the same thing,
just add a sign - after division.

The base 2 expansion of a number can be found by repeated division by 2, recording the remainders, and concatenating those remainders, starting with the last. The difference for the base -2 is the remainders may be negative. In this case, we add the quotient by 1 and add the remainder by 2 to make the remainders be positive.
Here is the explanation:
Let d represents the quotient and r represents the remainder, then
n = d * (-2) + r = d * (-2) + 2 - 2 + r = (d + 1) * (-2) + (r + 2).

Code

C++ Code for Convert to base -2

class Solution {
public:
     string baseNeg2(int N) {
        string res = "";
        while (N) {
            res = to_string(N & 1) + res;
            N = -(N >> 1);
        }
        return res == "" ? "0" : res;
    }
};

Java Code for Convert to base -2

class Solution {
    public String baseNeg2(int N) {
       StringBuilder res = new StringBuilder();
        while (N != 0) {
            res.append(N & 1);
            N = -(N >> 1);
        }
        return res.length() > 0 ? res.reverse().toString() : "0";
    }
}

Python Code for Convert to base -2

class Solution:
     def baseNeg2(self, x):
        res = []
        while x:
            res.append(x & 1)
            x = -(x >> 1)
        return "".join(map(str, res[::-1] or [0]))

Complexity Analysis for  Convert to Base -2 LeetCode Solution

Time Complexity

O(Log n)

Space Complexity

O(Log n)

Reference: https://en.wikipedia.org/wiki/Negative_base

Translate »