Find the Median

Problem description

The median of a list of numbers is essentially its middle element after sorting. The same number of elements occur after it as before. Given a list of numbers with an odd number of elements, find the median?

Input Format

The first line contains the integer n, the size of arr. The second line contains n space-separated integers arr[i].

Constraints

• 1 <= n <= 1000001
• n is odd
• -10000 <= arr[i] <= 10000

Link to the problem on hackerrank

Explanation

As n is odd is one of the consteaint we donot need to worry about the even cases.

We will use Arrays.sort() to sort the array and just print the middle element of the array as the output.

Solution in java

import java.util.*;
class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        System.out.println(arr[(n+1)/2 - 1]);
        sc.close();
    }
}