#include <bits/stdc++.h>

string convertBase(int n)

{

// Write Your Code Here.

string result="";

while(n){

if(n&1){

result="1"+result;

}

else{

result="0"+result;

}

n=-(n>>1);

}

return result=="" ? "0" :result;

}

Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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”.

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

```
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

```
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’.
```

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

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

```
1 <= T <= 50
0 <= N <= 10^9
Time limit: 1 sec
```

```
2
6
2
```

```
11010
110
```

```
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.
```

```
2
5
8
```

```
101
11000
```

Hint

The remainder should always be positive.

Approaches

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'

All tags

Sort by

Interview problems

Easy Peasy Solution By NK

#include <bits/stdc++.h>

string convertBase(int n)

{

// Write Your Code Here.

string result="";

while(n){

if(n&1){

result="1"+result;

}

else{

result="0"+result;

}

n=-(n>>1);

}

return result=="" ? "0" :result;

}

2 views

0 replies

1 upvote

Interview problems

java soln easy

import java.util.* ;

import java.io.*;

public class Solution {

public static String convertBase(int n){

// Write your code here.

StringBuffer s = new StringBuffer();

String res=" ";

if(n==0)

{

return "0";

}

while(n!=0)

{

int rem=n%-2;

n=n/-2;

if(rem<0)

{

rem=1;

n+=1;

}

s.insert(0,rem);

}

res =s.toString();

return res;

}

}

10 views

0 replies

0 upvotes

Interview problems

C++ Code

#include <bits/stdc++.h>

string convertBase(int n)

{

// Write Your Code Here.

string ans="";

while(n){

ans = to_string(n&1)+ans;

n = -(n>>1);

}

return ans == "" ? "0" : ans;

}

32 views

0 replies

0 upvotes