# Top Five Average

Posted: 27 Feb, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
`````` Approach 1

Approach: We can sort the list ‘RECORDS’ in non-decreasing order of IDs, and in case IDs are equal we sort them in non-increasing order of scores.  Now, if the first entry of a player is found at index ‘i’ in list ‘RECORDS’ then its top 5 scores are between index ‘i’ and ‘i+4' inclusive.

Algorithm:

1. Sort the list ‘RECORDS’ in non-decreasing order of IDs, and in case IDs are equal sort them in non-increasing order of scores.
2. Create a list ‘TOPFIVEAVERAGES’.
3. Run a loop where ‘i’ ranges from 0 to ‘N’ - 1 and in each step do the following.
• If ID of RECORDS[i] equals ‘COMPLETED’ then continue.
• Otherwise, let ‘AVERAGE’ := (RECORDS[i].SCORE + RECORDS[i+1].SCORE + … + RECORDS[i + 4].SCORE) / 5. And append [RECORDS[i].ID, AVERAGE] in list     ‘TOPFIVEAVERAGES’.
4. Return ‘TOPFIVEAVERAGES’.