273. The Median
Foundation1000 ms256 MBSolved by 0%
Print the median of n integers.
When n is odd this is the middle value. When n is even there are two
middle values, and this problem asks for the SMALLER of them, so that the answer
is always one of the input values and never a fraction.
1 2 3 -> 2
1 2 3 4 -> 2 (the smaller of 2 and 3)
One index expression handles both cases, and finding it is the exercise.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the median as defined above.
Input3
3 1 2
Output2
Noteis an odd count, so the middle value is unambiguous
Input4
1 2 3 4
Output2
Noteis an even count, taking the SMALLER of the two middles
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.