Assign the Assignments

Easy
0/40
Average time to solve is 10m
profile
Contributed by
19 upvotes
Asked in companies
MicrosoftAmazonUnthinkable Solutions

Problem statement

Ninja and his friend are working on an assignment that contains ‘N’ tasks. Each task has a complexity ‘C[i]’.

Ninja wants to assign ‘B’ number of tasks to his friend and ‘A’ number of tasks to himself. Given that he can only assign tasks with complexity greater than or equal to 'X' to himself and tasks with complexity less than 'X' to his friend.

So help Ninja to find how many ways are there to choose ‘X’ such that Ninja gets ‘A’ and his friend gets ‘B’ number of tasks.

Note : 
The complexity of each task is pairwise distinct.
For example : 
N a b
5 3 2
C: 5 19 2 62 1
Here ‘X’ can be 2,3,4 as 3 tasks have greater complexity that will be assigned to Ninja and the remaining two will be assigned to NInja’s friend.
So the answer is 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then test cases follow:

The first line contains three integers ‘N’, ‘A’, and ‘B’ representing the total number of tasks, number of tasks that will ninja solve, and the number of tasks that ninja’s friend will solve.

The second line contains  ‘N’ space-separated elements denoting the complexity of each task.
Output Format : 
For each test case, return an integer denoting the number of ways to choose ‘X’ as described in the problem.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
2 <= N <= 10^5
1 <= A,B <= N
1 <= C[i] <= 10^9    

Time Limit: 1 sec
Sample Input 1 :
2
5 2 6
1 2 3 4 5
4 2 2
10 12 16 14
Sample Output 1 :
0
2
Explanation of Sample Input 1 :
For the first test case, we cannot take any value of ‘X’ that can divide the task as required so return 0.
For the second test case, we take ‘X’ as 12 and 13 so answer is 2.
Sample Input 2 :
2
6 3 3
4 8 12 16 20 24
2 1 1
1 1
Sample Output 2 :
4
0
Hint

Try to sort the complexities of the task and then find the value of ‘X’.

Approaches (1)
Greedy Method

Firstly, if the sum of ‘A’, ‘B’ > ‘N’ then simply we will return 0 as it is not possible to assign more tasks than ‘N’.

 

Then, we need to find all those ‘X’ on which atleast ‘B’ number of tasks have complexity less than ‘X’ and atleast ‘A’ number of tasks have complexity greater than ‘X’.

 

Now, If ‘A’ + ‘B’ <= ‘N’, then we will first sort the array and then select first ‘B’ number of tasks for Ninja’s friend and the last ‘A’ tasks are for Ninja. So we will take the difference between C[B-1] and C[N-A] as on all these values C[B-1], C[B-1]+1, C[B-1]+2, …….., C[N-A]-1 of ‘X’ atleast ‘B’ tasks will be less or equal complexity which will be assigned to the Ninja's friend and ‘A’ tasks will have greater complexity than ‘X’ which will be assigned to Ninja.

Time Complexity

O(N*logN), where ‘N’ is the number of tasks given in the problem.

 

As we are sorting the complexities of the task which will take O(N*logN).

Space Complexity

 O(1),

 

As we are not storing anything.

Code Solution
(100% EXP penalty)
Assign the Assignments
Full screen
Console