Last Updated: 14 Apr, 2021

Convert to base '-2'

Moderate

Problem statement

Given a number 'N', you need to find a string having “1” or “0” that is equivalent to the value of integer 'N' in base “-2”.

Note:

The resulting string must not have leading zeros unless the string is “0”.

For Example:

If 'N' = 4, then its value in base ‘-2’ will be “100” as 0*(-2)^0 +0*(-2)^1 + 1*(-2)^2 = 4.

Input Format:

The first line contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains a single integer denoting ‘N’.

Output Format:

For each test case, return a string denoting the value of ‘N’ in base ‘-2’.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
0 <= N <= 10^9

Time limit: 1 sec

Solve now

Approaches

01 Approach

We can solve this problem as we do for positive bases. The main thing is that remainder should always be a positive number which is the contradicting point in negative bases.

Let us understand this with an example.

Let’s say ‘N’ = -5 and ‘BASE’ = -2. Now on dividing -5 by -2 we will get a quotient = 2 and remainder = -1.

Writing -5 according to remainder formula, we get -5 = 2*(-2) + -1.( dividend = quotient*divisor + remainder)

The remainder should always be positive, and here the remainder is negative.

If we right ‘-5’ as -5 = 3*(-2) + 1, we can get a positive remainder.

We can say that whenever the remainder is negative, we can make it positive by incrementing the quotient by ‘1’ and remainder by ‘2’.

So the idea to convert the given number to base ‘-2’ is the same as we do in base positive ‘2’ with an extra point that whenever the remainder comes negative, we will increment the ‘N’ by ‘1 remainder by ‘2’.

Algorithm

If 'N' is ‘0’ return “0”.
Initialize a string 'RES' to store the resulting string.
Run a loop until 'N' is not ‘0’.
- Store remainder obtained by dividing “N” by ‘-2’ in a variable ‘REM’.
- Divide “N” by ‘-2’.
- If ‘REM’ is negative.
  - Increment 'N' by ‘1’.
  - Increment ‘REM' by ‘2’.
- Add ‘REM’ to the ‘RES’ string.
Reverse ‘RES’ and return it.

Solve now