DAA Lab program to perform heap sort

DAA LAB Program 3

||Write a program to perform heap sort.||

#include<stdio.h>
#include<conio.h>
void heapsort(int[], int);
void heapify(int[], int);
void adjust(int[], int);
int main()
{
int array[50],n,i;
clrscr();
printf("Enter the no. of elements to be sorted:\n ");
scanf("%d",&n);
printf("Enter %d elements: \n",n);
for(i=0 ; i<n ; i++)
{
scanf("%d",&array[i]);
}
heapsort(array,n);
printf("Sorted list in ascending order using heap sort is:\n");
for(i = 0; i < n; i++)
{
printf("%d\t", array[i]);
}
printf("\n");
getch();
return 0;
}
void heapsort(int array[], int n)
{
int i,t;
heapify(array,n);
for(i=n-1 ; i>0 ; i--)
{
t = array[0];
array[0] = array[i];
array[i] = t;
adjust(array,i);
}
}
void heapify(int array[], int n)
{
int item,i,j,k;
for(k=1 ; k<n ; k++)
{
item = array[k];
i = k;
j = (i-1)/2;
while( (i>0) && (item>array[j]) )
{
array[i] = array[j];
i = j;
j = (i-1)/2;
}
array[i] = item;
}
}
void adjust(int array[], int n)
{
int item,i,j;
j = 0;
item = array[j];
i = 2*j+1;
while(i<=n-1)
{
if(i+1 <= n-1)
if(array[i] < array[i+1])
i++;
if(item < array[i])
{
array[j] = array[i];
j = i;
i = 2*j+1;
}
else
break;
}
array[j] = item;
}


OUTPUT

Posted by No comments:

DAA Lab program to perform selection sort

DAA LAB  Program 2

||Write a program to perform selection sort.||

#include<stdio.h>
#include<conio.h>
void main()
{
clrscr();
int i,position,swap,a[100],d,n;
printf("Enter The No. Of Elements\n");
scanf("%d",&n);
printf("Enter %d Integers\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<(n-1);i++)
{
position=i;
for(d=c+1;d<n;d++)
{
if(array[position]>array[d])
position=d;
}
if(position!=i)
{
swap=a[i];
a[i]=a[position];
a[position]=swap;
}
}
printf("Sorted List in Ascending Order is:\n");
for(i=0;i<=n;i++)
{
printf("%d\t",a[i]);
}
getch();

output 




Posted by No comments:

DAA Lab program to perform insertion sort

DAA LAB Program 1

||Write a program to perform insertion sort.||

#include<stdio.h>
#include<conio.h>
void main()
{
clrscr();
int i,t,a[100],d,n;
printf("Enter The No. Of Elements\n");
scanf("%d",&n);
printf("Enter %d Integers\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n-1;i++)
{
d=i;
while(d>0&&a[d]<a[d-1])
{
t=a[d];
a[d]=a[d-1];
a[d-1]=t;
d--;
}
}
printf("Sorted List in Ascending Order is:\n");
for(i=0;i<=n-1;i++)
{
printf("%d\t",a[i]);
}
getch();

}

OUTPUT



Posted by No comments:

HackerRank Solutions | Hacker Rank Solutions

HackerRank  Solutions


 
 

Posted by 1 comment:

C Program to implement SLR Parser

/* C program to implement Simple LR Parser. */

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

int i,j,k,m,n=0,o,p,ns=0,tn=0,rr=0,ch=0;
char read[15][10],gl[15],gr[15][10],temp,templ[15],tempr[15][10],*ptr,temp2[5],dfa[15][15];

struct states
{
    char lhs[15],rhs[15][10];
    int n;
}I[15];

int compstruct(struct states s1,struct states s2)
{
    int t;
    if(s1.n!=s2.n)
        return 0;
    if( strcmp(s1.lhs,s2.lhs)!=0 )
        return 0;
    for(t=0;t<s1.n;t++)
        if( strcmp(s1.rhs[t],s2.rhs[t])!=0 )
            return 0;
    return 1;
}

void moreprod()
{
    int r,s,t,l1=0,rr1=0;
    char *ptr1,read1[15][10];

    for(r=0;r<I[ns].n;r++)
    {
        ptr1=strchr(I[ns].rhs[l1],'.');
        t=ptr1-I[ns].rhs[l1];
        if( t+1==strlen(I[ns].rhs[l1]) )
        {
            l1++;
            continue;
        }
        temp=I[ns].rhs[l1][t+1];
        l1++;
        for(s=0;s<rr1;s++)
            if( temp==read1[s][0] )
                break;
        if(s==rr1)
        {
            read1[rr1][0]=temp;
            rr1++;
        }
        else
            continue;

        for(s=0;s<n;s++)
        {
            if(gl[s]==temp)
            {
                I[ns].rhs[I[ns].n][0]='.';
                I[ns].rhs[I[ns].n][1]=NULL;
                strcat(I[ns].rhs[I[ns].n],gr[s]);
                I[ns].lhs[I[ns].n]=gl[s];
                I[ns].lhs[I[ns].n+1]=NULL;
                I[ns].n++;
            }
        }
    }
}

void canonical(int l)
{
    int t1;
    char read1[15][10],rr1=0,*ptr1;
    for(i=0;i<I[l].n;i++)
    {
        temp2[0]='.';
        ptr1=strchr(I[l].rhs[i],'.');
        t1=ptr1-I[l].rhs[i];
        if( t1+1==strlen(I[l].rhs[i]) )
            continue;

        temp2[1]=I[l].rhs[i][t1+1];
        temp2[2]=NULL;

        for(j=0;j<rr1;j++)
            if( strcmp(temp2,read1[j])==0 )
                break;
        if(j==rr1)
        {
            strcpy(read1[rr1],temp2);
            read1[rr1][2]=NULL;
            rr1++;
        }
        else
            continue;

        for(j=0;j<I[0].n;j++)
        {
            ptr=strstr(I[l].rhs[j],temp2);
            if( ptr )
            {
                templ[tn]=I[l].lhs[j];
                templ[tn+1]=NULL;
                strcpy(tempr[tn],I[l].rhs[j]);
                tn++;
            }
        }

        for(j=0;j<tn;j++)
        {
            ptr=strchr(tempr[j],'.');
            p=ptr-tempr[j];
            tempr[j][p]=tempr[j][p+1];
            tempr[j][p+1]='.';
            I[ns].lhs[I[ns].n]=templ[j];
            I[ns].lhs[I[ns].n+1]=NULL;
            strcpy(I[ns].rhs[I[ns].n],tempr[j]);
            I[ns].n++;
        }

        moreprod();
        for(j=0;j<ns;j++)
        {
            //if ( memcmp(&I[ns],&I[j],sizeof(struct states))==1 )
            if( compstruct(I[ns],I[j])==1 )
            {
                I[ns].lhs[0]=NULL;
                for(k=0;k<I[ns].n;k++)
                    I[ns].rhs[k][0]=NULL;
                I[ns].n=0;
                dfa[l][j]=temp2[1];
                break;
            }
        }
        if(j<ns)
        {
            tn=0;
            for(j=0;j<15;j++)
            {
                templ[j]=NULL;
                tempr[j][0]=NULL;
            }
            continue;
        }

        dfa[l][j]=temp2[1];
        printf("\n\nI%d :",ns);
        for(j=0;j<I[ns].n;j++)
            printf("\n\t%c -> %s",I[ns].lhs[j],I[ns].rhs[j]);
        getch();
        ns++;
        tn=0;
        for(j=0;j<15;j++)
        {
            templ[j]=NULL;
            tempr[j][0]=NULL;
        }
    }
}

void main()
{
    FILE *f;
    int l;
    clrscr();

    for(i=0;i<15;i++)
    {
        I[i].n=0;
        I[i].lhs[0]=NULL;
        I[i].rhs[0][0]=NULL;
        dfa[i][0]=NULL;
    }

    f=fopen("tab6.txt","r");
    while(!feof(f))
    {
        fscanf(f,"%c",&gl[n]);
        fscanf(f,"%s\n",gr[n]);
        n++;
    }

    printf("THE GRAMMAR IS AS FOLLOWS\n");
    for(i=0;i<n;i++)
        printf("\t\t\t\t%c -> %s\n",gl[i],gr[i]);

    I[0].lhs[0]='Z';
    strcpy(I[0].rhs[0],".S");
    I[0].n++;
    l=0;
    for(i=0;i<n;i++)
    {
        temp=I[0].rhs[l][1];
        l++;
        for(j=0;j<rr;j++)
            if( temp==read[j][0] )
                break;
        if(j==rr)
        {
            read[rr][0]=temp;
            rr++;
        }
        else
            continue;
        for(j=0;j<n;j++)
        {
            if(gl[j]==temp)
            {
                I[0].rhs[I[0].n][0]='.';
                strcat(I[0].rhs[I[0].n],gr[j]);
                I[0].lhs[I[0].n]=gl[j];
                I[0].n++;
            }
        }
    }
    ns++;

    printf("\nI%d :\n",ns-1);
    for(i=0;i<I[0].n;i++)
        printf("\t%c -> %s\n",I[0].lhs[i],I[0].rhs[i]);

    for(l=0;l<ns;l++)
        canonical(l);

    printf("\n\n\t\tPRESS ANY KEY FOR DFA TABLE");
    getch();
    clrscr();

    printf("\t\t\tDFA TABLE IS AS FOLLOWS\n\n\n");
    for(i=0;i<ns;i++)
    {
        printf("I%d : ",i);
        for(j=0;j<ns;j++)
            if(dfa[i][j]!='\0')
                printf("'%c'->I%d | ",dfa[i][j],j);
        printf("\n\n\n");
    }
    printf("\n\n\n\t\tPRESS ANY KEY TO EXIT");
    getch();
}


Input File For SLR Parser:

S S+T
S T
T T*F
T F
F (S)
F t
Posted by No comments:

Hacker Rank Solutions For Sherlock-and-Pairs

Sherlock is given an array of N integers A0, A1 ... AN-1 by Watson. Now Watson asks Sherlock that how many different pairs of indices i and j exist such that i is not equal to j but Ai is equal to Aj.

That is, Sherlock has to count total number of pairs of indices (i, j) where Ai = Aj AND i ≠ j.

Input Format 

First line contains T, the number of testcases. T test case follows.

Each testcase consists of two lines, first line contains an integer N, size of array.

Next line contains N space separated integers.

Output Format 

For each testcase, print the required answer in different line.

Constraints 

1 ≤ T ≤ 10

1 ≤ N ≤ 105

1 ≤ A[i] ≤ 106

Sample input

2

3

1 2 3

3

1 1 2

Sample output

0

2

Explanation 

In the first testcase, no two pair of indices exist which satisfy the given property.

In second testcase as A[0] = A[1] = 1, the pairs of indices (0,1) and (1,0) satisfy the given property.


Solution:

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

int main() {

    int t,T,n,i,j,temp;
    long long int count,k;
    scanf("%d",&T);
    int c[1000000] = {0};
    for(t=0;t<T;t++){
        scanf("%d",&n);
        int a[n];
        count =0;
        for(i=0;i<n;i++){
            scanf("%d",&temp);
            c[temp-1]++ ;
        }
        for(i=0;i<1000000;i++){
            if(c[i]>1){
                k = c[i];
                count+= k*(k-1);
            }
           
            c[i] = 0;
        }
       
        printf("%lld\n",count);
    }
    return 0;
}


Posted by No comments:

Hacker Rank Solutions for Sherlock-and-Watson

John Watson performs an operation called Right Circular Rotation on an integer array a0,a1 ... an-1. Right Circular Rotation transforms the array from a0,a1 ... aN-1 to aN-1,a0,... aN-2.

He performs the operation K times and tests Sherlock's ability to identify the element at a particular position in the array. He asks Q queries. Each query consists of one integer x, for which you have to print the element ax.

Input Format

The first line consists of 3 integers N, K and Q separated by a single space.

The next line contains N space separated integers which indicates the elements of the array A.

Each of the next Q lines contain one integer per line denoting x.

Output Format 

For each query, print the value in the location in a newline.

Constraints 

1 ≤ N ≤ 105

1 ≤ A[i] ≤ 105

1 ≤ K ≤ 105

1 ≤ Q ≤ 500

0 ≤ x ≤ N-1

Sample input

3 2 3

1 2 3

0

1

2

Sample output


2

3

1

Explanation 

After one rotation array becomes, 3 1 2.

After another rotation array becomes 2 3 1.

Final array now is 2,3,1.

0th element of array is 2.

1st element of array is 3.

2nd element of array is 1.

Solution:

#include<stdio.h>

int main(){
    int n,k,q,temp,x,i;
    scanf("%d %d %d",&n,&k,&q);
    int a[n],b[n];
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    k = k % n;
    
    for(i=0;i<n;i++){
        temp = (i+n-k)%n;
        a[i]=b[temp];   
    }
    for(i=0;i<q;i++){
        scanf("%d",&x);
        printf("%d\n",a[x]);
    }
    return 0;
}

Posted by No comments:

Hacker Rank Solution for The-Full-Counting-Sort

Problem Statement

In this challenge you need to print the data that accompanies each integer in a list. In addition, if two strings have the same integers, you need to print the strings in their original order. Hence, your sorting algorithm should be stable, i.e. the original order should be maintained for equal elements.

Insertion Sort and the simple version of QuickSort were stable, but the faster in-place version of Quicksort was not (since it scrambled around elements while sorting).

In cases where you care about the original order, it is important to use a stable sorting algorithm. In this challenge, you will use counting sort to sort a list while keeping the order of the strings (with same accompanying integer) preserved.

Challenge
In the previous challenge, you created a "helper array" that contains information about the starting position of each element in a sorted array. Can you use this array to help you create a sorted array of the original list?

Hint: You can go through the original array to access the strings. You can then use your helper array to help determine where to place those strings in the sorted array. Be careful about being one off.

Details and a Twist

You will be given a list that contains both integers and strings. Can you print the strings in order of their accompanying integers? If the integers for two strings are equal, ensure that they are print in the order they appeared in the original list.

The Twist - Your clients just called with an update. They don't want you to print the first half of the original array. Instead, they want you to print a dash for any element from the first half. So you can modify your counting sort algorithm to sort the second half of the array only.

Input Format 

n - the size of the list ar.

n lines follow, each containing an integer x, and a string, s.

Output Format 

Print the strings in their correct order.

Constraints 

1 <= n <= 1000000

n is even

1 <= length(s) <= 10

0 <= x < 100 , x ∈ ar

The characters in every string s is in lowercase.

Sample Input

20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the
Sample Output

- - - - - to be or not to be - that is the question - - - -
Explanation
Below is the list in the correct order. The strings of each number were printed above for the second half of the array. Elements from the first half of the original array were replaced with dashes.

0 ab
0 ef
0 ab
0 ef
0 ij
0 to
1 be
1 or
2 not
2 to
3 be
4 ij
4 that
4 is
4 the
5 question
6 cd
6 gh
6 cd
6 gh

Program:
import java.io.*;
  import java.util.*;
 
  public class Solution {    
      public static void main(String[] args) {
          Scanner in = new Scanner(System.in);
          int s = in.nextInt();
         HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
         HashMap<Integer, ArrayList<Integer>> index_Map = new HashMap<Integer, ArrayList<Integer>>();
        int[] count = new int[100];
        for(int i=0;i<s;i++){
             int key = in.nextInt();
             count[key]++;
             String value = in.next();
             if(!map.containsKey(key)){
                 map.put(key, new ArrayList<String>());
                 index_Map.put(key, new ArrayList<Integer>());
             }
             index_Map.get(key).add(i);
             map.get(key).add(value);
        }
       
        int mid = s/2;
        StringBuffer sb = new StringBuffer();
        for(int i = 0;i < 100;i++ )
        {
            if(map.containsKey(i)){
                for(int j = 0;j < map.get(i).size();j++){
                    int index = index_Map.get(i).get(j);
                    String string = map.get(i).get(j);
                    if(index < mid)
                        sb.append("-").append(" ");
                    else
                        sb.append(string).append(" ");
                }
            }
        }
        System.out.println(sb.toString());                  
     }  
 }

Posted by 5 comments:

Hacker Rank Solutions for The-Love-Letter-Mystery

James got hold of a love letter that his friend Harry has written for his girlfriend. Being the prankster that James is, he decides to meddle with it. He changes all the words in the letter into palindromes.

While modifying the letters of the word, he follows 2 rules:

(a) He always reduces the value of a letter, e.g. he changes 'd' to 'c', but he does not change 'c' to 'd'.

(b) If he has to repeatedly reduce the value of a letter, he can do it until the letter becomes 'a'. Once a letter has been changed to 'a', it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations he carries out to convert a given string into a palindrome.



Input Format 

 The first line contains an integer T, i.e., the number of test cases.
The next T lines will contain a string each.



Output Format 
A single line containing the number of minimum operations corresponding to each test case.



Constraints 
1 ≤ T ≤ 10

1 ≤ length of string ≤ 10000

All characters are lower cased english letters.



Sample Input
 #00


3

abc

abcba

abcd



Sample Output 
#00


2

0

4



 Explanation


For the first test case, ab*c* -> ab*b* -> ab*a*.


For the second test case, abcba is a palindromic string.


For the third test case, abc*d* -> abc*c* -> abc*b* -> abc*a* = ab*c*a -> ab*b*a.


Program:
#include<stdio.h>
#include<math.h>
#include<string.h>

main() 
{
    int n;
    scanf("%d", &n);
    int i,l,a,j;
    char s[10][10000];
    for(i=0;i<n;i++){
        scanf("%s",s[i]);
        l = strlen(s[i]);
        a=0;
            for(j=0;j<l-j-1;j++){
                if(s[i][j]!=s[i][l-j-1]){
                    a+=abs(s[i][j]-s[i][l-j-1]);
                }
            }
            printf("%d \n",a);
       
    }   
}



Posted by 1 comment:

Hacker Slotions for Two-arrays


You are given two integer arrays, A and B, each containing N integers. The size of the array is less than or equal to 1000. You are free to permute the order of the elements in the arrays.

Now here's the real question: Is there an arrangement of the arrays, such that, Ai+Bi ≥ K for all i, where Ai denotes the ith element in the array A.




Input Format


The first line contains an integer, T, the number of test-cases. T test cases follow. Each test case has the following format:

The first line contains two integers, N and K. The second line contains N space separated integers, denoting array A. The third line describes array B in a same format.



 Output Format


For each test case, if such an arrangement exists, output "YES", otherwise "NO" (without quotes).




Constraints

1 <= T <= 10

1 <= N <= 1000

1 <= K <= 109

0 <= Ai, Bi ≤ 109




Sample Input

2


3 10

2 1 3

7
8 9

4 5

1 2 2 1

3 3 3 4



Sample Output

YES

NO



Explanation

The first input has 3 elements in Array A and Array B, we see that the one of the arrangements, 3 2 1 and 7 8 9 has each pair of elements (3+7, 2 + 8 and 9 + 1) summing upto 10 and hence the answer is "YES".

The second input has array B with three 3s. So, we need at least three numbers in A that are greater than 1. As this is not the case, the answer is "NO".





Program
#include<stdio.h>

void ascending(int *a,int size){
    int i,j,t;
    for(i=0;i<size;i++){
        for(j=i+1;j<size;j++){
            if( *(a+i)> *(a+j)){
                t= *(a+i);
                *(a+i)= *(a+j);
                *(a+j)= t;
            }
        }
    }
}
void descending(int *a,int size){
    int i,j,t;
    for(i=0;i<size;i++){
        for(j=i+1;j<size;j++){
            if( *(a+i)< *(a+j)){
                t= *(a+i);
                *(a+i)= *(a+j);
                *(a+j)= t;
            }
        }
    }
}


main (){
    int t,i,j,temp,flag;
    scanf("%d",&t);
    int n,k;
    for(i=0;i<t;i++){
        scanf("%d %d",&n,&k);
        int a[n],b[n];
        for(j=0;j<n;j++){
            scanf("%d",&a[j]);
        }
        for(j=0;j<n;j++){
            scanf("%d",&b[j]);
        }
        ascending(a,n);
        descending(b,n);
        flag=1;
        for(temp=0;temp<n;temp++){
            if((a[temp]+b[temp])<k)
                flag=0;
        }
        if(flag==1)
            printf("YES\n");
        else
            printf("NO\n");
    }
}



Posted by No comments:

print Fahrenheit-Celsius table with a heading for fahr = 0, 20, ..., 300; floating-point version

#include<stdio.h>

/*
Exercise 1-3.
Modify the temperature conversion program to print
a heading above the table.
*/

/* print Fahrenheit-Celsius table with a heading
for fahr = 0, 20, ..., 300;
floating-point version */

int main()
{
float fahr, celsius;
float lower, upper, step;

lower = 0; /* lower limit of temperature scale */
upper = 300; /* upper limit */
step = 20; /* step size */

fahr = lower;
printf("Fahr\tCentigrade\n");
while (fahr <= upper) {
celsius = (5.0 / 9.0) * (fahr - 32.0);
printf("%3.0f\t%6.1f\n", fahr, celsius);
fahr = fahr + step;
getch();
}
}
  
OUTPUT:

Fahr                    Centigrade
  0                             -17.8
Posted by No comments:
Subscribe to: Posts (Atom)