Last Updated: 11 Aug, 2022

Median Marks

Hard

Asked in company

Solve now

Problem statement

There are 'N' students in a class, where 'N is odd'. The 'ith' student wants their marks to be in the range 'L[i]' to 'R[i]' (both inclusive). The teacher can give a total of at most 'X' marks to students. To show that the result is good, the teacher wants the median marks to be as large as possible.

Return the maximum median marks the teacher can obtain provided they optimally distribute the 'X' marks among students satisfying the ranges.

To find the median of a sequence of odd length, you have to sort it and take the element in the middle position after sorting.

It is guaranteed that the teacher has enough marks to give, i.e. L[1]+L[2]+.....+L[N] <= 'X'.

For Example:-

Let 'N' = 3, 'X' = 13, 'L' = [2, 3, 5], 'R' = [4, 5, 7].
We can assign 2 marks to the first student, 5 marks to the second student, and 5 marks to the third student.
So the median mark is 5 which is the maximum possible.

Input Format:-

First-line contains an integer 'T', which denotes the number of test cases.
For every test case:-
First-line contains two integers 'N' and 'X'.
Second-line contains 'N' space-separated integers, the elements of the array 'L'
Third-line contains 'N' space-separated integers, the elements of the array 'R'.

Output Format:-

For each test case, Return the maximum median marks you can obtain.

Note:-

You don’t need to print anything. Just implement the given function.

Constraints:-

1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'L[i]' <= 'R[i]' <= 10^5
1 <= 'X' <= 10^8
'N' is odd.

The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:-

Assign ‘left’= 1 and ‘right’= 10^5. While doing a binary search, we find ‘mid’ from ‘left’ and ‘right’, and for every ‘mid’ we check if it is possible to get the median equal to 'mid' or not.
If it is possible then we store ‘mid’ in our answer and assign left to mid+1, otherwise assign right to mid-1.
For checking, we can call the 'helper' function.
In helper function: -
We can divide the students into three groups.
- R[i] < mid.
- L[i] >= mid.
- L[i] < mid <= R[i].
In order for the median marks to be at least 'mid', there must be at least (N+1)/2 marks greater than or equal to 'mid'. Let's denote the number of such marks as 'count'.
The first group can't increment the value of 'count' so it is beneficial to give minimum marks to this group.
The second group always increments the value of 'count', so it is beneficial to give minimum marks to this group.
Now for the third group, we can give 'mid' marks to max(0, ((N+1)/2 - 'count')) students and for the remaining student, we can give L[i] marks.

Algorithm:-

Initialize variables 'ans' with 1, 'left' with 1, 'right' with 10^5.
while(left <= right) :
- mid=(left+right)/2;
- If (helper(mid, N, X, L, R) == 1) :
  - 'ans' = 'mid'.
  - 'left' = 'mid'+1.
- Else :
  - right' = 'mid'-1.
Return 'ans' which is the required answer.

=> helper function:-

Creating 'totalMarks', 'count', and 'extra'.
Iterate 'i' from 0 to 'N'-1:
- If(R[i] < mid):
  - totalMarks+=L[i];
- Else if (L[i]>=mid):
  - totalMarks+=L[i];
  - count++;
- Else:
  - extra.push_back(L[i]);
Now in extra, we can give 'mid' marks to max(0, ((N+1)/2 - 'count')) students and for the remaining student, we can give L[i] marks, And also add the marks we give to 'totalMarks'.
If (totalMarks <= X):
- Return 1;
Else :
- Return 0;

Solve now