Find the Median – HackerRank Solution

In this post, we will solve Find the Median HackerRank Solution. This problem (Find the Median) is a part of HackerRank Problem Solving series.

Solution – Find the Median – HackerRank Solution

C++

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

void quickselect(vector<int> &v, int begin, int end, int median_idx) {
    if (end - begin <= 1)
        return;

    int a, b;
    int pivot = v[end - 1];

    a = begin;
    b = end - 1;

    while (b > a) {
        if (v[b - 1] > pivot) {
            v[b] = v[b - 1];
            b--;
        } else {
            int tmp = v[b - 1];
            v[b - 1] = v[a];
            v[a] = tmp;
            a++;
        }
    }

    v[b] = pivot;

    if (begin <= median_idx && b >= median_idx) {
        quickselect(v, begin, b, median_idx);
    } else if (b + 1 <= median_idx && end >= median_idx) {
        quickselect(v, b + 1, end, median_idx);
    }
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> input(n);
    for (auto &a : input)
        std::cin >> a;

    quickselect(input, 0, input.size(), input.size() / 2);

    std::cout << input[input.size() / 2] << std::endl;

    return 0;
}

Python

#!/bin/python3

import sys

def findMedian(arr):
    arr = sorted(arr)
    return arr[len(arr)//2]

if __name__ == "__main__":
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    result = findMedian(arr)
    print(result)

Java

import java.util.*;

public class Solution {

    public static double median(List<Integer> list) {
        if ((list.size() & 1) == 1) {
            return list.get(list.size() / 2);
        } else {
            int midSize = list.size() / 2;
            return (list.get(midSize - 1) + list.get(midSize)) / 2.0;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            int pos = Collections.binarySearch(list, a);
            if (pos < 0) {
                pos = Math.abs(pos) - 1;
            }
            list.add(pos, a);
            System.out.println(median(list));
        }
    }
}

Note: This problem (Find the Median) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.