RANDOMIZED QUICK SORT C/C++ PROGRAM

Its obvious that Quick sort performs at O(nlogn) running time, but the worst case running time of Quick sort is O(n ^2).
When does this case happen? It happens when a pivot was chosen such that the array is not divided into two haves i.e
      consider 1,2,3,4,5 when 5 is chosen as pivot ,
AFTER PARTITION
                                             left subarray : 1,2,3,4
                                             right subarray : (empty)

when this trend continues we actually perform n times the sorting function and since each call performs a partition O(n) total complexity is O(n*n) i.e O(n^2)

Hence to avoid this situation we chose pivot randomly instead of choosing the last element as pivot(traditional way)

you can however argue that even choosing the pivot randomly can lead to worst case, but statistically the probablity for such case to occur is low compared to normal way.

Here is the C++ code (To Convert to C code just replace cin,cout with printf,scanf)

CODE:
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

int partition(int *a,int p,int r)
{
srand(time(0));
int pivot = rand()%(r-p);
pivot += p;
swap(a[r],a[pivot]);
pivot = r;
int temp = a[r];
int i = p-1;
for (int j = p; j < r ;j++) {
if ( a[j] <  temp ) {
i++;
swap (a[i],a[j]);
}
}
i++;
swap (a[r],a[i]);
return i;
}


void quicksort(int *a,int p,int r)
{
if (p < r)
{
int q = partition(a,p,r);
quicksort(a,p,q);
quicksort(a,q+1,r);
}
}

int main() {
// your code goes here
int a[] ={2,5,6,2,1,9,8};
quicksort (a,0,6);
for (int i=0;i<7;i++)
cout << a[i] << endl;
return 0;
}

CALCULATING THE SIZE OF STRUCTURE IN C/C++:

consider a strucure

struct X
{
    short s; 
    int   i; 
    char  c; 
             
};

what do you think the size of structure will be? 2 + 4 + 1 ?

Sorry, then you are wrong. Because to reduce the lookup time by CPU compiler pads up the bytes untill it becomes a multiple of 4. This is however dependent on hardware,but most compilers does so.

so what happens is 

struct X
{
    short s; /* 2 bytes */
             /* 2 padding bytes */
    int   i; /* 4 bytes */
    char  c; /* 1 byte */
             /* 3 padding bytes */
};

but this is not the best way to declare the struct , why? because you waste space due to  padding of bytes. So here are some tricks to reduce the eat up of byte padding







struct Y
{
    int   i; /* 4 bytes */
    char  c; /* 1 byte */
             /* 1 padding byte */
    short s; /* 2 bytes */
};

struct Z
{
    int   i; /* 4 bytes */
    short s; /* 2 bytes */
    char  c; /* 1 byte */
             /* 1 padding byte */
};

POST YOUR DOUBTS IN THE COMMENTS

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;

SPOJ : ACPC 10D Trigraphs Solution

This problem could be solved by using DP.
Step 1:
        Initialse the adjacent nodes to the source node.
Step 2:
        Loop Across the other i nodes from 2 to N and initialise them.

P re-Requesite: DP
     However Learning Floyd Warshall Algorithm would help you in solving this problem.



Code:


#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

int main()
{
int i=1;
while(1) {
int n;
cin >>n;
if(n==0)
return 0;
int a[n][3];
for (int i=0;i<n;i++)
cin >>a[i][0]>>a[i][1]>>a[i][2];
cout<<i<<". ";
if(n==1)
cout<<a[0][1]<<endl;
else {
                                                               // Initialisation Step
a[1][0] += a[0][1];
a[0][2] += a[0][1];
a[1][1] += min(min(a[1][0],a[0][1]),a[0][2]);
a[1][2] += min(min(a[0][2],a[0][1]),a[1][1]);


                                                                 // Calculating the remaing nodes
for(int i  = 2 ; i<n;i++)
{
a[i][0] += min(a[i-1][0],a[i-1][1]);
a[i][1] += min(min(min(a[i][0],a[i-1][0]),a[i-1][1]),a[i-1][2]);
a[i][2] += min(min(a[i][1],a[i-1][1]),a[i-1][2]);
}
cout <<a[n-1][1]<<endl;
i++;
}
}
return 0;
}

SPOJ : KURUK 14 (Genie Sequence)

Hints: Consider the fact that for a sequence to be a genie sequence all the possible positions must be satisfied

Solution:
consider 6 elements 5 4 3 2 1 0
This forms a genie sequence as all the possible positions are covered respectively
But the position can be from either sides i.e the first number can be 5 or 0
                                                                       second number can be 4 or 1
                                                                       third number can be 3 or 2
and so on...
notice that sum of this combination ie always n - 1 here it is 6 - 1 = 5
(5+0) , (4+1),(3+2)... = 5

->  Thus create an array and input elements,intialise the array to 0
for each element mark in the arrray as 1 if it is already marked 1 , then mark the pair of that element..
for example if 5 is entered mark array[5] = 1 , but if 5 is entered again mark array[ n - 1 - 5] = 1

->after this process again iterate through the array, if u encounter an element with value 0 that means this cant form a genie sequence..


C code:
#include <stdio.h>
#include <stdlib.h>

int main(void) {
int t,n,temp,i,j,flag;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int *a;
flag = 0;
a = calloc(n+1,sizeof(int));
for ( i = 0 ; i < n ; i++)
{
scanf("%d",&temp);
if(temp < n)
{
if(a[temp] == 0)
a[temp] = 1;
else
a[n -1 - temp] = 1;

}
}

for( i = 0 ; i<n;i++)
{

if(a[i] == 0)
{
flag  = 1;
break;
}
}
if(flag == 1)
printf("NO\n");
else
printf("YES\n");
}

return 0;

}

SPOJ : MANGOES Solution

Hints:
Just catch the point that GCD of 3 consecutive numbers must be 1.

Solution:
If GCD of three consecutive numbers is 1,the first number cant be an even  number because then the third number would obviously be an even number and so GCD wont be 1 

example
2,3,4
when first number if even (2) third number will be even(4) and GCD wont be 1 here it is 2.
So the first number must be an odd number ex:3,4,5 
Now comes the logic for three consecutive numbers only 2 can be a factor common to all three(if u cant figure out why feel free to comment or mail me,will reply ASAP)
so number of magoes = sum of numbers that satisfy the condition which in case is only the odd numbers
* Sum of odd numbers starting from 1 is n*n where n is the number of terms, here the number of terms is (N-1)/2
so number of mangoes is (N-1)/2*(N-1)/2
But we are required to give a number less than N so take modulo %

Here is the C code:

#include <stdio.h>

int main(void) {
long long int t,n,m;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
m = (n -1)/2;
m = m*m;
m = m %n;
printf("%lld\n",m);
}
return 0;

}

SPOJ : ACT solution (Alpha Centauri Tennis)

Spoj:ACT question

Hints: 
The winner of the match is the winner of the last game

Solution:

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


int main()
{
    int t,n;
    char *s;
    scanf("%d",&t);
    s = (char*)malloc(1000);

    while(t--)
    {
       
        scanf("%d %s",&n,s);
n=strlen(s)-1;
        printf("%c\n",s[n]);
    }
return 0;