Convert to base '-2'

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
2 upvotes

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6
2
Sample Output 1:
11010
110
Explanation Of Sample Input 1:
Test Case 1: Value of  string “11010” in base ‘10’ = 0*(-2)^0 +1*(-2)^1 + 0*(-2)^2 +1*(-2)^3 +1*(-2)^4 = 0 + (-2) + 0 + (-8) + (16) = 6.

Test Case 2: Value of  string “110” in base ‘10’ = 0*(-2)^0 +1*(-2)^1 + 1*(-2)^2 = 0 + (-2) + 4 = 2.
Sample Input 2:
2
5
8
Sample Output 2:
101
11000
Hint

The remainder should always be positive.

Approaches (1)
Base Conversion.

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.
Time Complexity

O(log(N)), where ‘N’ is the given number.

 

In each iteration, we are dividing the problem to half value. So the time complexity is O(log(N)).

Space Complexity

O(log(N)), where ‘N’ is the given number.

 

We are using a string “res” to store the resulting string, and for any number “N”, the maximum length of the string will be log(N). So the space complexity is O(log(N)).

Code Solution
(100% EXP penalty)
Convert to base '-2'
Full screen
Console