DIARY

QUESTION- http://www.spoj.com/problems/GCPC11F

SOURCE CODE-


//http://www.spoj.com/problems/GCPC11F/
#include<stdio.h>
#include<string.h>
int main()
{
    int t,i,count,shift,max;
    char s[2000];
    scanf("%d",&t);
        getchar();
    while(t--)
    {
        gets(s);
        char p[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
        int hash[26];
        for(i=0;i<26;i++)
                hash[i]=0;
        int len=strlen(s);
        for(i=0;i<len;i++)
        {
            if(s[i]!=' ')
            {
                hash[s[i]-65]++;
            }
        }
        max=0;
        count=0;
        int pos;
        for(i=0;i<26;i++){
                if(hash[i]>max){
                        max=hash[i];
                        pos=i;
                        }
                //printf("%c %d ",i+65,hash[i]);
        }
        for(i=0;i<26;i++)
        {
                if(hash[i]==max)
                        count++;
        }
        int d;
        if(count>1)
                printf("NOT POSSIBLE\n");
        else
        {
                //printf("%d ",pos);
                shift=pos-4;
                if(shift<0)
                        shift=shift+26;
                printf("%d ",shift);
                for(i=0;i<len;i++)
                {
                        if(s[i]!=' ')
                        {
                                d=s[i]-65;
                                d=d-shift;
                                //printf("%d ",d);
                                if(d<0)
                                        d=d+26;
                                s[i]=p[d];
                        }
                        
                }
                printf("%s\n",s);
        }
    }
    return 0;
}

HOW MANY GAMES (SPOJ)

EXPLAINATION//


Write the average score x as a reduced fraction x=p/q. 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.

basically we have to convert the avg into fraction part p/q then calculate the gcd(p,q) 
answer will be q/gcd(p,q)



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<len;j++)
{
if(s[j]!='.')
num=10*num+(s[j]-'0');
}
pow=1;
if(flag==0){
for(i=0;i<count;i++)
{
pow=pow*10;
}
}
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<len_replace)
new_length=len_txt+count*(len_pattern-len_replace)
else there is no need to resize the string .
*/


#include<stdio.h>//stdio.h
#include<string.h>//string.h
#include<stdlib.h>//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<len_txt;i++)
        {
            if(q<=size&&a[q]==i)
            {
                k=0;
                while(k<len_replace)
                {
                    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;
}

Knuth (Fisher-Yates) algorithm

/* microsoft
Write a function that gets a number n and prints out a random list
of numbers 1..n to the screen. For example:

randlist(5) : 1 5 3 2 4
randlist(6) : 4 6 1 5 3 2

This should be truly random (uniformly spread) and with a O(n) complexity.
Every number should appear only once. Random(n) is given as a tool you can use to generate a
single random number between 1-n */
//algorithm knuth suffle algo//
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,i=0,temp=0;
scanf("%d",&n);
int ar[n];
for(i=0;i<n;i++)
ar[i]=i+1;
while(i>0)
{
int r = rand()%i;//which is similar to ->rand()%i;
        temp = ar[i-1];
        ar[i-1] = ar[r];
        ar[r] = temp;
        i-=1;
}
for(i=0;i<n;i++)
printf("%d ",ar[i]);
return 0;
}

Colours A, B, C, D

#include<stdio.h>
#include<string.h>

char S[2][100005];

void swap(char* a, char* b)
{
    char temp = *a;
    *a = *b;
    *b = temp;
}

int main()
{
   int i,j,N,flag[4]={0};
   scanf("%d",&N);
   scanf("%s",S);
   
   
   for(i=0;i<2*N;i+=2)
   {   
       flag[0] = flag[1] = flag[2] = flag[3] = 1;
       flag[S[0][i] - 'A'] = flag[S[0][i+1] - 'A'] = 0;
       
       for(j=0; j<=3; j++)
       {
           if(flag[j]) { flag[j] = 0; S[1][i] = j+65; break; }
       }
       
       for(j=0; j<=3; j++)
       {
           if(flag[j]) { flag[j] = 0; S[1][i+1] = j+65; break; }
       }
       
       if(S[1][i] == S[1][i-1]){
        swap(&S[1][i], &S[1][i+1]);
        /*char ch=S[1][i];
        S[1][i]=S[1][i+1];
        S[1][i+1]=ch;*/
        }
   }
   
   printf("%s",S[1]);
  return 0;      
}

BINARY STAIRLING NUMBER

//http://www.spoj.com/problems/BINSTIRL/
#include<stdio.h>
int main()
{
int t,n,k;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&k);
if((n-k)&(k-1)/2)
printf("0\n");
else
printf("1\n");
}
return 0;
}

FIND THE CLONES SPOJ

//http://www.spoj.com/problems/CLONE/

//
#include<stdio.h>
#include<algorithm>
using namespace std;
int arr[100000]={0};
int main()
{
         int a,b,i,j,count,temp,val;
long double check,sum;
        scanf("%d %d",&a,&b);
        //int arr[2100];
        while(a&&b)
        {
                char s[100];
//int arr[a];
int hash[25000]={0};
                //k=1;
               
                        for(i=0;i<a;i++)
{
val=0;
scanf("%s",s);
for(j=0;j<b;j++)
{
if(s[j]=='A')
val=val*10+1;
else if(s[j]=='C')
val=val*10+2;
else if(s[j]=='G')
val=val*10+3;
else if(s[j]=='T')
val=val*10+4;
}
arr[i]=val;
                }

                sort(arr,arr+a);
               // int hash[a];
int k;
                /*for(k=0;k<=a;k++){
                        hash[k]=0;
//printf("%d ",arr[k]);
} */     
                count=1;
int flag=0;
check=arr[0];
for(i=1;i<a;i++)
{
if(arr[i]==check)
{
flag=0;
count++;
}
else
{
flag=1;
hash[count]++;
count=1;
check=arr[i];
}
}
hash[count]++;
                for(i=1;i<=a;i++)
                        printf("%d\n",hash[i]);
                //printf("\n");
                scanf("%d %d",&a,&b);
        }
        return 0;
}

LATGACH3 SPOJ

//http://www.spoj.com/problems/M3TILE/
//explaination- http://www.algorithmist.com/index.php/UVa_10918
#include<stdio.h>
int main()
{
        int i,n;
        int f[31];
        int g[31];
        f[0]=1,f[1]=0;
        g[0]=0,g[1]=1;
        for(i=2;i<31;i++)
        {
                f[i]=f[i-2]+2*g[i-1];
                g[i]=f[i-1]+g[i-2];
        }
        scanf("%d",&n);
        while(n!=-1)
        {
                printf("%d\n",f[n]);
                scanf("%d",&n);
        }
        return 0;
}

ambiguous permutation SPOJ

//http://www.spoj.com/problems/PERMUT2/
/*
the inverse permutation is one where the i-th number is the position of the integer i in the permutation.
 It is ambiguous if it is identical to the normal representation of the permutation.
  For example, if { 2, 3, 4, 5, 1 } is a permutation, then it's inverse is { 5, 1, 2, 3, 4 }
   and in this case is not ambiguous.
*/
#include<stdio.h>
int main()
{
int hash[100005];
int i,n;
scanf("%d",&n);
while(n!=0)
{
int arr[n+1];
for(i=1;i<=n;i++){
scanf("%d",&arr[i]);
hash[arr[i]]=i;
}
for(i=1;i<=n;i++)
{
if(arr[i]!=hash[i])
break;
}
if(i==n+1)
printf("ambiguous\n");
else
printf("not ambiguous\n");
scanf("%d",&n);
}
return 0;
}

The Mad Numerologist SPOJ

//http://www.spoj.com/problems/MADN/
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
        int t,n,i,a,k=1;
        scanf("%d",&t);
        while(t--)
        {
                int v[200];
                int c[200];
                scanf("%d",&n);
                 char vowel[] = {'A', 'U', 'E', 'O', 'I'};
        char conso[] ={'J', 'S' , 'B' , 'K' , 'T','C','L','D','M','V','N','W','F','X','G','P','Y','H','Q','Z','R'};
                int vowel_count=0,conso_count=0;
                for(i=1;i<=n;i++)
                {

if(i&1){
a=vowel[vowel_count/21];
v[vowel_count]=a;
vowel_count++;
}
else
{
a=conso[conso_count/5];
c[conso_count]=a;
conso_count++;
}
                }
sort(v,v+vowel_count);
sort(c,c+conso_count);
vowel_count=0,conso_count=0;
printf("Case %d: ",k);
for(i=1;i<=n;i++)
{
if(i&1){
printf("%c",v[vowel_count]);
vowel_count++;
}
else{
printf("%c",c[conso_count]);
conso_count++;
}
}
                printf("\n");
k++;
        }
        return 0;
}

GENERATE UNIQUE RANDOM NUMBER

/* microsoft INTERVIEW QUESTION 
Write a function that gets a number n and prints out a random list
of numbers 1..n to the screen. For example:

randlist(5) : 1 5 3 2 4
randlist(6) : 4 6 1 5 3 2

This should be truly random (uniformly spread) and with a O(n) complexity.
Every number should appear only once. Random(n) is given as a tool you can use to generate a
single random number between 1-n */
//algorithm knuth suffle algo//
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,i=0,temp=0;
scanf("%d",&n);
int ar[n];
for(i=0;i<n;i++)
ar[i]=i+1;
while(i>0)
{
int r = rand()%i;//which is similar to ->rand()%i;
        temp = ar[i-1];
        ar[i-1] = ar[r];
        ar[r] = temp;
        i-=1;
}
for(i=0;i<n;i++)
printf("%d ",ar[i]);
return 0;
}

SPOJ LOGIC

// formula used n!+2^n-n 
#include<stdio.h>
#include<math.h>
int main()
{
/*unsigned long long int factorial[]={ 1, 1 , 2 , 6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000, 6402373705728000};*/
unsigned long long int t,ans,fect,pow,p,n;
scanf("%llu",&t);
fect=1;
p=t;
n=t;
while(t>0)
{
fect=fect*t;
t--;
}
//printf("%llu ",fect);
pow=1;
while(p>0)
{
pow=pow*2;
p--;
}
//printf("%llu ",pow);
ans=fect+pow-n;
printf("%llu\n",ans);
        return 0;

}