Description

Let's say you're a data analyst at a hospital with a database containing patient age information. You've been tasked with designing an algorithm to find the median age of the patients in O(n) time complexity.

 

Your goal is to devise an algorithm that efficiently finds the median age among these ages and maintains a time complexity of O(n) even with a substantial amount of data.

 

In this context, the median is the number that appears in the middle when all ages are arranged in ascending order. For an odd number of data points, the median is the exact middle number after sorting. For an even number of data points, the median is the floor of the average of the two middle numbers.

 

Hint:

The worst case of quicksort is O(n²) and there is worst case in the testcase.

How to avoid it?

 

Note: Among STL data structure, only vector is allowed to use. To get full score, you need to find out a O(n) solution.

* sorting functions, like sort in <algorithm> or qsort in <stdlib.h>, which can directly sort the array are prohibited

(You can import <algorithm> or <stdlib.h> but don't use sort or qsort function)

* Data structure like <set>, <priority_queue>, <ordered_set>, <list>, are also prohibited

* The random function which can generate random value is allowed.

Random function tutorial:

https://www.geeksforgeeks.org/rand-and-srand-in-ccpp/

Input

The first line has an integer number, N, indicates there are N patients in the hospital

The second line contains N unique unsorted integer ages of paitents.

 

Constraint:

0 < N < 10000000

0 <= ages <= 2^31 - 1

Output

Print the median age of the patients

Note that you need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss