All Tracks>Problem
Median
★★★★★

4

1 votes
Problem

There are N students in a class and each student has got a positive integer from 0 to 100 (inclusive). Your task is to find the median of marks of the class. If N is even then return the value on the smaller side (refer to sample 2). 

Note : Median is the value of the middle element in a sorted array.

 

INPUT FORMAT

  •  First line contains the number of testcases T
  •  First line of each testcase contain an integer N
  •  Second line conatins N-space separated integers denoting the marks of each student

OUTPUT FORMAT

  •  Output a single integer - Median of marks of the class

CONSTRAINT

  •  1 <= T <= 500
  •  1 <= N <= 105
  •  0 <= Marks[i] <= 100 ( Marks of i-th student) 

SUBTASK

  •  Subtask 1 : 1 <= N <= 5000
  •  Subtask 2 : original constraint
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

Sample 2:

The sorted array is {2, 5, 8, 10}. As n=4 is even and there is no atomic middle element we choose the value on the lower side i.e. 5

Editor Image

?