Library Problem

A giant library has just been inaugurated this week. It can be modeled as a sequence of N consecutive shelves with each shelf having some number of books. No, think of the following two queries which can be performed on these shelves.
● Change the number of books in one of the shelves.
● Obtain the number of books on the shelf having the kth rank within the range of shelves.
A shelf is said to have the kth rank if its position is k when the shelves are sorted based on the number of the books they contain, in ascending order. Can you write a program to simulate the above queries?
Input Format :
The first line contains a single integer T, denoting the number of test cases. The first line of each test case contains an integer N denoting the number of shelves in the library. The next line contains N space separated integers where the ith integer represents the number of books on the ith shelf where 1<=i<=N. The next line contains an integer Q denoting the number of queries to be performed. Q lines follow with each line representing a query. Queries can be of two types:
● 1 x k - Update the number of books in the xth shelf to k (1 <= x <= N).
● 0 x y k - Find the number of books on the shelf between the shelves x and y (both inclusive) with the kth rank (1 <= x <= y <= N, 1 <= k <= y-x+1).
Output Format For every test case, output the results of the queries in a new line.
Sample Input :
2
2
1 2
2
0 1 2 1
0 1 2 2
4
4 3 2 1
4
0 1 1 1
1 1 1
0 1 1 1
0 14 3
Sample Output:
1
2
4
1
2
Sample C Code:

#include <stdio.h>

int sort(int x,int y,int sortarr1[]); // sort the array in ascending order
int updatenob(int x,int y,int k,int arr1[]); //update the number of books

int sort(int x,int y,int sortarr1[]){ //sorting the array in ascending order

int i,j;
for(i=0;i<y-x+1;i++){
for(j=0;j<y-x+1;j++){
if(sortarr1[i]<sortarr1[j]){
int temp=sortarr1[i];
sortarr1[i]=sortarr1[j];
sortarr1[j]=temp;
}
}
}
}

int updatenob(int x,int y,int k,int arr1[]){ //update the number of books

int i,j;
int sortarr1[y-x+1];
int a=x-1;
for(i=0;a<y;i++,a++){
sortarr1[i]=arr1[a];
}
sort(x,y,sortarr1);
printf("The Number of Books in K(th) Position is : %d \n", sortarr1[k-1]);
}

int main(){
int i,j,k,t,n,q,nq;
int books[n];
int query[4];

printf("Plese Enter The Number of Test Cases: \n"); //get the number of test cases
scanf("%d",&t);

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

printf("Plese Enter The Number of Shelves: \n"); //get the number of shelves
    scanf("%d",&n);

printf("Plese Enter The Number of Books in Each Shelves: \n"); //Number of books in each shelf
for(j=0;j<n;j++){
        scanf("%d", &books[j]);
}
 
printf("Plese Enter The  Number of Queries You Want: \n"); //get the number of queries you want to do
      scanf("%d", &nq);

for(j=0;j<nq;j++){

printf("Plese Enter The Query Code: \n"); //get the query code
        scanf("%d",&q);
     
if(q==0){
    for(k=0;k<3;k++){
    scanf("%d",&query[k]);
}

updatenob(query[0],query[1],query[2],books);

}
else if(q==1){ //change the number of books query
for(k=0;k<2;k++){
    scanf("%d",&query[k]);
}

books[query[0]-1]=query[1];

}
else{
printf("Entered Query Code is Wrong \n");
}
}
}
return 0;
}

Comments

Popular posts from this blog

Programming Using GNU Octave

What Is A Gamma Ray Burst?