2

Top Five Average

Difficulty: MEDIUM
Avg. time to solve
10 min
Success Rate
90%

Problem Statement
Suggest Edit

You are given a list ‘Records’ of size ‘N’, representing runs scored by different Cricket players in different matches, where Records[i] = [ID_i, Score_i] represent one score of the player with ‘ID_i’.

Your task is to find each player’s top 5 scores average. Return a list ‘topFiveAverages’ where topFiveAverages[j] = [ID_j, top_five_average_j] represents a player with ID_j and floor value of average of his 5 highest scores. The list ‘topFiveAverages’ should be sorted in increasing order of IDs.

Note:

1. It is guaranteed that for each player, there are at least 5 entries of his scores in the list ‘Records’.
2. You need to find the floor value of the top 5 scores average.
3. Different players have different IDs.

Example:

Consider a List ‘Records’ = [[1, 10], [1, 11], [2, 13], [2, 15], [1, 9], [2, 1], [1, 21], [2, 21], [2, 1], [1, 19], [1, 9], [2, 11], [1, 7]],  
Clearly, there are two players, with ID 1 and 2, respectively.
The top 5 scores of the player with ID 1 are 21, 19, 11, 10, 9, and the average of these scores is 14.
The top 5 scores of the player with ID 2 are 21, 15, 13, 11, 1, and the average of these scores is 12.
Thus, we should return a list ‘topFiveAverages’ = [[1, 14], [2, 12]]
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases, then ‘T’ test cases follow.

The first line of each test case consists of a single integer ‘N’, representing the size of the list ‘Records’.

Then next ‘N’ lines follow in each test case, and each of these ‘N’ lines consists of two space-separated integers, represent the ID and Score of the player.
Output format:
For each test case, in a separate line, print 2*K space-separated integers, where ‘K’ is the number of unique players in ‘Records’. The Id and top 5 average of the player having the ith smallest ID are given by (2*i + 1)th and (2*i + 2)th integer respectively.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
1 <= ID <= 10^9
0 <= Score <= 10^5 

Time limit: 1 sec
Sample Input 1:
2
5
7 0
7 0
7 0
7 0
7 0
13
1 10
1 11
2 13
2 15
1 9
2 1
1 21
2 21
2 1
1 19
1 9
2 11
1 7
Sample Output 1:
7 0
1 14 2 12
Explanation For Sample Input 1:
Test case 1:
There is only one player having ID 7, and his all 5 scores are 0,  Thus top 5 scores average of this player will also be 0, so the list ‘topFiveAverages’ should be [[7, 0]] 

Test case 2:
See the problem statement for an explanation.
Sample Input 2:
1
5
1 1
1 2
1 3
1 4
1 5
Sample Output 2:
1 3
Explanation For Sample Input 2:
Test case 1:
There is only one player having ID 1, and his all 5 scores are 1, 2, 3, 4 and 5.  Thus top 5 scores average of this player will be 3, so the list ‘topFiveAverages’ should be [[1, 3]] 
Reset Code
Full screen
copy-code
Console