Below given code is for nbin spoj or new binary spoj.
Now let formulate the table:
Number of Bits 
Binary number at given Nth position 
Given N 
1 
1

1

2 
10

2

3 
100

3

3 
101

4

4 
1000

5

4 
1001

6

4 
1010

7

5 
10000

8

5 
10001

9

5 
10010

10

5 
10100

11

5 
10101

12

From the above table we can see that five digit binary number can accommodate at most 5 values .
Now by carefully seeing this we can see that if remove the two Most significant Bit from five digit binary number we can see that rest binary number are the number less than three digit binary as see below
10

000 
10

001 
10

010 
10

100 
10

101 
Position of the array represent the number of Bits and content of array represent the maximum “N” that or less can be represented using that or less number of Bit :
PRE_COMPUTE[i] = PRE_COMPUTE[i1] + PRE_COMPUTE[i2] + 1;
Now for getting result take the string of MAX = 72(because (N = 10^{15 } ) Nth number can be accommodated in at max 72 Bit you will get that after calculating) initially containing all ZEROES now for the given “N” find the minimum POSITION in array which can accommodate Nth number and after that make N = N  PRE_COMPUTE[POSITION 1]  1 .And repeat till N>0;(you will get this if you use pen and paper and write few steps)
#include <bits/stdc++.h> using namespace std; #define LL long long #define LEN 72 LL pre_com[100]; void pre() { pre_com[1] = 1; pre_com[2] = 2; pre_com[3] = 4; pre_com[4] = 7; int i=4; while(pre_com[i] <=1000000000000000LL) { i++; p[i] = p[i2]+1; pre_com[i] =pre_com[i1] + pre_com[i2]+1; } } int find(LL n) { int low=0,high=LEN,mid; mid = (low + high)>>1; while(true) { mid = (low + high)>>1; if(pre_com[mid] < n) { if(pre_com[mid + 1] >n) return mid; else low = mid; } else { if(pre_com[mid  1] < n) return mid  1; else high = mid; } } } void print(LL n) { bool a[80]={false}; int pos = find(n); int max = pos + 1; a[pos+1]=true; LL diff = n  pre_com[pos]  1; while(diff>0) { pos = find(diff); a[pos+1] = true; diff = diff  pre_com[pos]  1; } for(int i=max ;i>=1;i) if(a[i]) printf("1"); else printf("0"); } int main() { pre(); int t; scanf("%d",&t); while(t) { LL n; scanf("%lld",&n); print(n); printf("\n"); } return 0; }