HOW MANY GAMES (SPOJ)

PROBLEM CODE :GAMES
12448. HOW MANY GAMES
Write the average score x as a reduced fraction x=pq. This means that p and q are integers, that q is positive and that q is minimal (or, equivalently, that p and q have no nontrivial common factor). Then the player can have played any multiple of q games hence the minimum number of games the player should have played is q.

When x=−30.25, note that −30.25=−1214 and −121 and 4 have no common factors except +1 and −1, hence the minimum number of games is indeed 4.

SOLUTION//


#include"stdio.h"
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        gcd(b,a%b);
}
int main()
{
int t,num,count,i,j,len,pow,flag;
char s[50];
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
len=strlen(s);
count=0,flag=1;
for(j=len-1;j>=0;j--)
{
if(s[j]=='.'){
flag=0;
break;
}
else
count++;
}
num=0;
for(j=0;j
{
if(s[j]!='.')
num=10*num+(s[j]-'0');
}
pow=1;
if(flag==0){
for(i=0;i
{
pow=pow*10;
}
}
//printf("%d %d",num,pow);
printf("%d\n",pow/gcd(num,pow));
}
return 0;
}

MICROSOFT INTERVIEW QUESTION

/* QUESTION--
//http://www.careercup.com/question?id=16392679
The problem is given a string s1= "ABCDBCCDABCD". and a pattern "BC". we have to replace this pattern with other string ("UVW" or "U"or "uv"). Do this without creating new string.
Take the case to replace "BC" with following
a) "uvw" s1=AUVWDUVWCDAUVWD .
b) "U" s1=AUDUCDAUD .
c) "UV" s1=AUVDUVCDAUVD .

*/
/*Explaination
USING THE KMP algo the times of occurence and position of given pattern in the text then stored the position of the pattern  in two arrays (array a and array b ) 
for e.g text="Chandan"
pat="an";
replace="QQQ";
then a[0]=2,a[1]=5 and b[0]=3,b[1]=6
array containing the position of starting index postion of pattern and array b contain the ending position of the pattern .
now if using the KMP algo count the number of occurence of pattern in text.
and resize the string 
if(len_pattern
new_length=len_txt+count*(len_pattern-len_replace)
else there is no need to resize the string .
*/


#include//stdio.h
#include//string.h
#include//stdlib.h
int a[400];//ARRAYS TO STORE THE POSITION OF THE PATTERN IN THE STRING
int b[400];
int q=0,p=0;
void computeLPSArray(char *pat, int M, int *lps);

int KMPSearch(char *pat, char *txt)
{
 int count=0;
    int M = strlen(pat);
    int N = strlen(txt);

    // create lps[] that will hold the longest prefix suffix values for pattern
    int *lps = (int *)malloc(sizeof(int)*M);
    int j  = 0;  // index for pat[]

    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);

    int i = 0;  // index for txt[]
    while(i < N)
    {
      if(pat[j] == txt[i])
      {
        j++;
        i++;
      }

      if (j == M)
      {
  count++;
        //printf("%d\n", i-j);
        a[q]=i-j;
        b[p]=(i-j+M-1);
        //printf("%d %d\n",a[q],b[p]);
        q++,p++;

        j = lps[j-1];
      }

      // mismatch after j matches
      else if(pat[j] != txt[i])
      {
        // Do not match lps[0..lps[j-1]] characters,
        // they will match anyway
        if(j != 0)
         j = lps[j-1];
        else
         i = i+1;
      }
    }
 return count;
    //free(lps); // to avoid memory leak
}

void computeLPSArray(char *pat, int M, int *lps)
{
    int len = 0;  // lenght of the previous longest prefix suffix
    int i;

    lps[0] = 0; // lps[0] is always 0
    i = 1;

    // the loop calculates lps[i] for i = 1 to M-1
    while(i < M)
    {
       if(pat[i] == pat[len])
       {
         len++;
         lps[i] = len;
         i++;
       }
       else // (pat[i] != pat[len])
       {
         if( len != 0 )
         {
      // This is tricky. Consider the example AAACAAAA and i =7.
           len = lps[len-1];

           // Also, note that we do not increment i here
         }
         else // if (len == 0)
         {
           lps[i] = 0;
           i++;
         }
       }
    }
}
int main()
{
    char txt[500],pat[500],replace[100];
    scanf("%s",txt);
    scanf("%s",pat);
    scanf("%s",replace);
    int len_txt=strlen(txt);
    int len_pat=strlen(pat);
    int len_replace=strlen(replace);
    int count=KMPSearch(pat, txt);

    int i,j,k,new_length;
    if(len_replace>=len_pat)
    {
        int increase_size=(len_replace*count)-(count*len_pat);
         new_length=len_txt+increase_size;
        txt[new_length];
        
        p=p-1;
       
        j=new_length-1;
        for(i=len_txt-1;i>=0;i--)
        {
            if(p>=0&&b[p]==i)
            {
                    k=len_replace-1;
                    while(k>=0)
                    {
                        txt[j]=replace[k];
                        k--;
                        j--;
                    }
                    p--;
                    i=i-len_pat+1;
            }
            else
            {
                txt[j]=txt[i];
                j--;
            }
        }
        printf("%s",txt);
    }
    else
    {
        int size=q-1;
        int decrease_size=(count*len_pat)-(count*len_replace);
        new_length=len_txt-decrease_size;
        j=0;
        q=0;
        for(i=0;i
        {
            if(q<=size&&a[q]==i)
            {
                k=0;
                while(k
                {
                    txt[j]=replace[k];
                    k++;
                    j++;
                }
                q++;
                i=i+len_pat-1;
            }
            else
            {
                txt[j]=txt[i];
                j++;
            }
        }
     txt[j]='\0';
        printf("%s",txt);
    }
    return 0;
}

DRUNKEN KNIGHT

In a bizarre game of chess ,knight was so drunk, that instead of his usual move he started walking straight. In every move Knight jumps on 2n steps forward (n is number of block that he had travelled so far from starting) but after that he has to take either 1 step forward or backward.
Now the Knight needs to get to position X so King (i.e. You) needs to decide the order of his backward or forward step in such a way that he can reach its destination in minimum number of steps. Remember he always travels in a straight line and the length of the board is infinite.
Input

The first line of the input contains an integer T denoting the number of test cases, for each test case enter value X ( i.e. destination)
Note : initially knight is at n = 1.
Output

For each test case the output should be string of numbers 1 & 2 where 1 denotes backward step and 2 denote the forward step
Note : for no solution print 0.
Constraints

1 ≤ T ≤ 100
1 ≤ X ≤ 10^10
Example

Input:
2
17
10
Output:
2111
0
Explanation

Case 1 : starting from n = 1 , knight moves to n = 3 ('2') , 5 ('1') , 9 ('1') , 17 ('1') i.e. string printed is 2 1 1 1
Case 2 : no solution is possible


SOLUTION--

#include
int main()
{
int t,i,len;
long long int num;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&num);
char str[40];
i=0;
//num=num-1;
if(num%2==0)
            printf("0\n");
        else{
while(num>0)
{
if(num%2==0)
str[i]='1';
else
str[i]='2';
i++;
num=num/2;
}
len=i-1;
for(i=len;i>0;i--)
printf("%c",str[i]);
printf("\n");
        }
}
return 0;
}