HRITHIK AGARWAL 20BCE2183
1. Some players play a game and their scores (positive integers) are recorded in the form of an array. A
player who scores more is the winner. Design an algorithm to find out the winner, next winner, worst
player, next worst player by scanning the score sheet only once.
Code:-
#include<stdio.h>
int main()
{
int n;
printf("Enter the total no. of players: \n");
scanf("%d",&n);
int score[n], arr[n];
printf("Enter the scores of each player: \n");
for(int i = 0;i < n; i++)
{
scanf("%d",&score[i]);
arr[i] = i;
}
for(int i = 0;i < n-1; i++)
{
if(score[i]>score[i+1])
{
int temp1 = score[i];
score[i] = score[i+1];
score[i+1] = temp1;
int temp2 = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp2;
i = -1;
}
}
printf("Winner: Player %d \n",arr[n-1]+1);
printf("Next Winner: Player %d \n",arr[n-2]+1);
printf("Worst Player: Player %d \n",arr[0]+1);
printf("Next Worst Player: Player %d \n",arr[1]+1);
return 0;
}
HRITHIK AGARWAL 20BCE2183
Output:-
HRITHIK AGARWAL 20BCE2183
2. Counting inversions
Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is
already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the
maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.
Code:-
#include<stdio.h>
int main()
{
int n, c = 0;
printf("Enter the total number of elements in array: ");
scanf("%d",&n);
int arr[n];
printf("Enter the elements:\n");
for(int i = 0; i < n; i++)
scanf("%d",&arr[i]);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(arr[i]>arr[j])
c++;
printf("Inversion count = %d",c);
return 0;
}
Output:-
HRITHIK AGARWAL 20BCE2183
3. Suppose an array A has n distinct integers. Write an algorithm to find an index k (k need not exist/
need not be unique) such that A[0].........A[k] is an increasing sequence and A[k+1]........A[n-1]is a
decreasing sequence.
Code:-
#include<stdio.h>
int main()
{
int n, flag=0;
printf("Enter the total number of distinct integers: ");
scanf("%d",&n);
int A[n];
printf("Enter the integers:\n");
for(int i = 0; i < n; i++)
scanf("%d",&A[i]);
for(int i = 0; i < n; i++) {
int c = 0;
for(int j = 0; j < i; j++) {
if(A[j] > A[j+1]) {
c += 1;
break;
}
}
for(int j = i+1; j < n-1; j++) {
if(A[j] < A[j+1]) {
c += 1;
break;
}
}
if(c == 0)
printf("Index %d is possible\n", i);
else
flag++;
}
if(flag == n)
printf("Index does not exist");
return 0;
}
Output:-
HRITHIK AGARWAL 20BCE2183
HRITHIK AGARWAL 20BCE2183
4. There are n items in the suitcase of a traveller. Onboarding the flight, the airline company told him that his
suitcase is overweight than the allowed capacity W and asked him deload some items and not to carry more
than W. He knows weight of each item. Devise an algorithm to find out which items to be discarded so that he
can carry max. weight W. (assume the weight of the suitcase is ignored)
Code:-
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }
void knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] +
K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
int res = K[n][W];
cout<<"\nResult of knapsack: "<<res;
w = W;
for (i = n; i > 0 && res > 0; i--) {
if (res == K[i - 1][w])
continue;
else {
cout<<"\nSelected weight: "<<wt[i - 1];
res = res - val[i - 1];
w = w - wt[i - 1];
}
}
}
int main()
{
int n,i;
cout<<"\nEnter number of elements in the knapsack: ";
cin>>n;
int val[50];
cout<<"\nEnter the value of "<<n<<" elements\n";
for(i=0;i<n;i++)
{
HRITHIK AGARWAL 20BCE2183
cin>>val[i];
}
int wt[50];
cout<<"\nEnter the weight of "<<n<<" elements\n";
for(i=0;i<n;i++)
{
cin>>wt[i];
}
int W;
cout<<"\nEnter the maximum capacity of knapsack: ";
cin>>W;
knapSack(W, wt, val, n);
return 0;
}
Output:-
HRITHIK AGARWAL 20BCE2183
5. There are n items in the suitcase of a traveler. On boarding theflight, the airline company told him that
his suitcase isover weightthan the allowed capacity W and asked himdeloadsome items and not to
carry more than W. He knows weight of each item and knows the priority (like which item is the most,
next most, etc.). Devise an algorithm to find out which items to be discardedbased onpriorityso that he
can carry max. weight W(assume the weight of the suitcase is ignored).
Code:-
#include<stdio.h>
int main()
{
int n,w,sum,diff;
printf("Enter the total number of items in the suitcase: ");
scanf("%d",&n);
int item[n],prior[n];
printf("Enter weight of each item: \n");
for(int i=0;i<n;i++)
{
scanf("%d",&item[i]);
sum = sum + item[i];
}
printf("Enter priority of each item (1-%d) : \n",n);
for(int i=0;i<n;i++)
scanf("%d",&prior[i]);
printf("enter the allowed capacity \n");
scanf("%d",&w);
for(int j=0;j<n-1;j++)
{
if(prior[j]>prior[j+1])
{
int temp1 = prior[j];
prior[j] = prior[j+1];
prior[j+1] = temp1;
int temp2 = item[j];
item[j] = item[j+1];
item[j+1] = temp2;
j = -1;
}
}
for(int i=0;i<n-1;i++)
{
if(sum>w)
{
sum = sum - item[i];
HRITHIK AGARWAL 20BCE2183
printf("removed item weight: %d \n",item[i]);
}
}
}
Output:-