why did we used unordered instead of ordered, what is the relation between the keys and the values in the way of ranks and marks
what if we used the ordered map
Problem
Submissions
Hints & solutions
Discuss
Class Test
Easy
0/40
Average time to solve is 10m
Contributed by
51 upvotes
Problem statement
Ninja recently appeared for a class test. The test was attended by ‘N’ students and the marks of each student was given in an array ‘A’.
Ninja knows that he got a rank ‘K’ among the ‘N’ students but forgot the marks achieved by him. The ranks are given according to the better marks scored by the students.
Tell the marks that must have been scored by Ninja to get a rank ‘K’.
Example :N = 5
K = 3
A = [ 2, 5, 4, 4, 5 ]
Rank 1 and Rank 2 students get marks = 5.
Rank 3 and Rank 4 students get marks = 4.
Rank 5 student gets marks = 2.
So, Ninja must have scored 4 marks in order to achieve Rank = 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains an integer ‘N’.
The second line of each test case contains an integer ‘K’.
The third line contains ‘N’ space separated integers denoting the elements of array ‘A’.
For each test case, print one integer denoting the score Ninja must have scored.
Print the output of each test case in a new line.
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^4
1 <= K <= N
0 <= A[i] <= 100
Time Limit: 1 sec
Sample Input 1 :
2
3
1
3 4 4
4
3
1 1 2 2
Sample Output 1 :
4
1
Explanation Of Sample Input 1 :
For test case 1 we have,
To get a Rank 1, Ninja must have scored maximum marks in the class.
Hence, Ninja scored 4 marks.
For test case 2 we have,
Students with marks = 2 will achieve ranks 1 and 2 respectively.
Students with marks = 1 will achieve ranks 3 and 4 respectively.
So, Ninja scored 1 mark.
Sample Input 2 :
3
2
1
20 9
2
1
9 17
7
2
9 6 0 2 20 10 5
Sample Output 2 :
20
17
10
Hint
Hint 1
Think about sorting the marks.
Approaches (1)
Approach 1
Optimal Greedy
Approach :
- Since ranks are achieved in order of marks by descending order.
- So, we first sort the marks in descending order.
- Now, the ranks are distributed to students from left to right.
- Then, the student with rank = ‘K’ will have marks at position ‘K-1’ in array ‘A’. ( Assume 0-based Indexing ).
Algorithm :
- Sort the input array ‘A’ in descending order.
- Return ‘A[K-1]’ as answer.
Time Complexity
O(N*logN) , where ‘N’ is the length of the array ‘A’.
Since we are sorting the array, the overall time complexity is O(N*logN).
Space Complexity
O(1)
Constant extra space is required. Hence, the overall Space Complexity is O(1).
Code Solution
(100% EXP penalty)
Class Test
All tags
Sort by
Interview problems
Easy C++ Solution
TC=O(nlogn)
Sc=n
#include <bits/stdc++.h>
int classTest(int n, vector<int> &a, int k) {
// Write your code here.
sort(a.rbegin(),a.rend());
unordered_map<int,int>m;
int c=1;
for (int i = 0; i < a.size(); i++) {
m[c] = a[i];
c++;
}
return m[k];
} 87 views
0 replies
0 upvotes
Interview problems
Code+Approach
#include <bits/stdc++.h>
int classTest(int n, vector<int> &arr, int k) {
sort(arr.begin(),arr.end());
return arr[n-k];
}
First sort all elements then we need to return n-k element.
For eg. to find score of rank 3 student having total 5 students , we will return arr[5-3] which is arr[2] position.
156 views
0 replies
2 upvotes
Interview problems
Easy Solution Alongwith Approach
CODE :
#include <bits/stdc++.h>
int classTest(int n, vector<int> &a, int k) {
// Write your code here.
sort(a.begin(),a.end());
int size=a.size();
int ans= a[size-k];
return ans;
}
Firstly, we'll sort the given array in increasing order using the sort function. Thereafter, we will create an ans integer variable in which we will store the answer which will be a[a.size()-k]. After this we will return the answer.
136 views
0 replies
1 upvote
Interview problems
best solution.
#include <bits/stdc++.h>
int classTest(int n, vector<int> &a, int k){
sort(a.begin() , a.end());
for(int j = 0 ; j<a.size() ; j++){
if(k == 1){
return *max_element(a.begin(),a.end());
}
else{
int p = n - k;
return (a[p]);
}
}
}
TC: O(logn)
SC: O(1)
140 views
0 replies
1 upvote
Interview problems
C++ BASIC || 2 APPROCHES
APR1:
#include <bits/stdc++.h> int classTest(int n, vector<int> &a, int k) { sort(a.begin(),a.end()); int count =0; for(int i=n-1;i>=0;i--) { count =count+1; if(count==k) { return a[i]; } } }
APR2:
#include <bits/stdc++.h> int classTest(int n, vector<int> &a, int k) { sort(a.begin(),a.end()); return a[n-k]; }
/*PLEASE UPVOTE IF FOUND USEFUL*/
105 views
0 replies
1 upvote
Interview problems
2 lines of code c++
#include <bits/stdc++.h>
int classTest(int n, vector<int> &a, int k) {
// Write your code here.
sort(a.rbegin(),a.rend());
return a[k-1];
}
115 views
1 reply
1 upvote
Interview problems
Easy code
int classTest(int n, vector<int> &a, int k) {
// Write your code here.
sort(a.begin(),a.end());
return a[n-k];
}
128 views
0 replies
1 upvote
Interview problems
easy code
int ans =0;
int rank=0;
sort(a.begin(),a.end());
for(int i=0;i<n;i++){
ans = i-k+1;
rank =a[ans];
}
return rank;
107 views
0 replies
1 upvote
Interview problems
3 line solution in c++
int classTest(int n, vector<int> &a, int k) { sort(a.begin(),a.end()); reverse(a.begin(),a.end()); return a[k-1]; }
148 views
5 replies
0 upvotes
1
2
C++ (g++ 5.4)
Console