AMUSING NUMBER (TSHOW1)

SPOJ Problem Set (classical)

11354. Amusing numbers

Problem code: TSHOW1

Amusing numbers are numbers consisting only of digits 5 and 6.Given an integer k , display the kth amusing number.

Input

FIrst line consists of integer N representing number of test cases

Next N lines consist of N integers (1<=k<=10^15)

Output

N lines each displaying corresponding kth amusing number

Example

Input:
2
1
5
Output:
5
65 



EXPLAINATION--

the sequence is : 5 , 6, 55, 56, 65, 66, 555, 565…

if we break the sequence by the length of each number i.e 5 and 6 are of length 1  whereas 55, 56 are of

length 2 and so on, it would make the problem easier to tackle. Suppose for time being we know that the

Kth  amusing number is of length x digits. We also magically know that its the Nth  number of length x.

(5 is the first number of length 1, 56 is second number of length 2 and so on…)

Then we can easily find the kth number by representing  the number (N-1) in its binary equivalent where

0 of binary stands for 5 and 1 of binary represents 6.

For instance : We need to find 5th amusing number and some how we  know it would be of length 2(x=2)

and 3rd(N=3) number of length  2.

Binary representation of N-1 =2 is : 10 , Replacing 0 by 5 and 1 by 6 we get : 65 which is the answer!

Now to find of what length the kth amusing number would be we  need to solve a GP.

There are 2 numbers of length 1,  4 numbers of length 2 , 8 numbers of length 3 and so on…

This is a GP  from which  we can easily find what length would be the kth amusing number and corresponding

value of N .

SERIES HINT--

KTH NUMBER  BINARY REPRESENTAION    AMUSING NUMBER

1                0                         5

2                1                         6

3               00                        55

4               01                        56

5               10                        65

6               11                        66

7              000                       555

8              001                       556

9              010                       565

10             011                       566

11             100                       655

12             101                       656

13             110                       665

14             111                       666

15            0000                      5555

16            0001                      5556

17            0010                      5565

18            0011                      5566

19            0100                      5655

20            0101                      5656

21            0110                      5665

22            0111                      5666

23            1000                      6555

24            1001                      6556

25            1010                      6565

26            1011                      6566

27            1100                      6655

28            1101                      6656

29            1110                      6665

30            1111                      6666

SOURCE CODE--

#include
#include
int main()
{
    int t;
    long long int num,temp,n,i,j,ans,k,rem;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&num);
        temp=0,n=0;

        //calculating the value of n(length)
        while(temp<num)
        {
            n=n+1;
            temp=pow(2,n+1)-2;
            //printf("%lld ",temp);
        }
        temp=pow(2,n)-2;
        //printf("%lld %lld\n",n,temp);
        ans=num-temp-1;
        char str[100000];
        int k=-1;

        //converting the number in binary representation
        while(ans>0)
        {
            rem=ans%2;
            k=k+1;
            str[k]=rem+'0';
            ans=ans/2;
        }
        j=n-k-1;
        for(i=1;i<=j;i++)
            printf("5");

        //print 5 inplace of '0' and print 6 in place of '1'
        for(i=k;i>=0;i--){
            if(str[i]=='0')
                printf("5");
            else
                printf("6");
        }
        printf("\n");
    }
    return 0;
}