SPOJ : NEG2 SOLUTION

I suggest you read wikipedia link. But i can summarise you in a nut shell. Our task is to convert the given decimal to a negative base(2) number to binary form
i.e take for example  7(base 10)

Basically pick the remainder as the positive even when remainder is negative (tricky pay attention!)

 7 = -3*-2 + 1. (least significant digit)
-3 =  2*-2 + 1
 2 = -1*-2 + 0
-1 =  1*-2 + 1
 1 =  0*-2 + 1. (most significant digit)

as you can notice in 2nd step -3 % -2 is actually -1, but we have to store as 1 as binary representation cant contain negative numbers.

so we add 1 to n/2 i.e  -3/-2  = 1 adding 1 we get 2 ( this ensures remainder is always postive)


posting the logic:

  string s="";
     if(n==0)
     {
             printf("0\n");
             return;
     }
     int i=-2;

     while(n)
     {
             if(n%i<0)
             {

             s=(char)(((n%i)+2)+'0')+s;   // When the remainder is negative 

             n=(n/i)+1;                    // adding one so that when divided remainder is > 0
             }
             else
             {
             s=(char)((n%i)+'0')+s;
             n=n/i;
             }

     }
    cout<<s;