HackerRank Find the Median Problem Solution

In this post, we will solve HackerRank Find the Median Problem Solution.

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?
Example
arr = [5, 3, 1, 2, 4]
The sorted array arr’ = [1, 2, 3, 4, 5]. The middle element and the median is 3.

Function Description

Complete the findMedian function in the editor below.

findMedian has the following parameter(s):

int arr[n]: an unsorted array of integers

Returns

int: the median of the array

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

Explanation 0
The sorted arr = [0, 1, 2, 3, 4, 5, 6]. It’s middle element is at arr[3] = 3.

Sample Input 0

7
0 1 2 4 6 5 3

Sample Output 0

HackerRank Find the Median Problem Solution

Find the Median C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

/**
Partition elements <= v[0] followed by elements >v[0].
Return the number of elements in the first "half".
*/
long partition(int *v, long len) {
    int pivot = v[0];
    long nextLeft = 1, nextRight = len-1;
    while (nextLeft <= nextRight) {
        if (v[nextLeft] <= pivot)
            nextLeft++;
        else
            swap(v + (nextRight--), v+nextLeft);
    }
    return nextLeft;
}

int findMax(int *v, long len) {
    long i;
    int max = v[0];
    for (i = 1; i < len; i++) {
        if (v[i] > max)
            max = v[i];
    }
    return max;
}

int findMin(int *v, long len) {
    long i;
    int min = v[0];
    for (i = 1; i < len; i++) {
        if (v[i] < min)
            min = v[i];
    }
    return min;
}

int findMedian(int *v, long len) {
    long toSkip = len / 2;
    long leftPartLen;
    while (len > toSkip) {
        if (toSkip == 0)
            return findMin(v, len);
        leftPartLen = partition(v, len);
        if (leftPartLen > toSkip) {
            // Search continues in the left partition.
            // The pivot is >= items in it.
            // If pivot is the median, return it otherwise remove it.
            // Not dropping the pivot would cause an infinite loop.
            if (leftPartLen == toSkip + 1)
                return v[0];
            
            v++;
            len = leftPartLen - 1;
        } else {
            // skip the left partition
            v += leftPartLen;
            len -= leftPartLen;
            toSkip -= leftPartLen;
        }
    }
    return findMax(v, len);
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    long n, i;
    int *ar;
    scanf("%ld\n", &n);
    ar = malloc(n * sizeof(*ar));
    for (i = 0; i < n; i++) {
        scanf("%d\n", &ar[i]);
    }
    printf("%d\n", findMedian(ar, n));
    free(ar);
    return 0;
}

Find the Median C++ Solution

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main(void)
{
    int n;
    cin >> n;
    vector<int> numbers;
    int mid = n / 2;

    copy_n(istream_iterator<int>(cin), n, back_inserter(numbers));
    nth_element(numbers.begin(), numbers.begin() + mid, numbers.end());

    cout << numbers[mid] << endl;
}

Find the Median C Sharp Solution

using System;
namespace Program{
  public class Solution{
    public static void Main(){
      int t = int.Parse(Console.ReadLine());
      string[] s= Console.ReadLine().Split(new char[]{' '});
      int[] A = new int[t];
      for(int i=0;i<t;i++)
        A[i]=int.Parse(s[i]);
      Array.Sort(A);
      Console.WriteLine(A[t/2]);
    }
  }
}

Find the Median Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'findMedian' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static int findMedian(List<Integer> arr) {
        Collections.sort(arr);
        return arr.get(arr.size() / 2);
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        int result = Result.findMedian(arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Find the Median JavaScript Solution

function processData(input) {
    input = input.split("\n");
    var size = parseInt(input[0]);
    var array = input[1].split(' ');
    array.splice(size, array.length);
    array = array.map(function(i) { return parseInt(i);});
    quickSort(array, 0, size-1);
    console.log(array[parseInt(array.length/2)]);
} 

function quickSort(array, start, end) {
    if (start < end) {
        var pivot = partition(array, start, end);
        // quickSort(array, start, pivot-1);
        // quickSort(array, pivot+1, end);
        var mid = parseInt(array.length/2);
        if (pivot>mid) {
            return quickSort(array, start, pivot-1);
        } else {
            return quickSort(array, pivot+1, end);
        }
    }
}

function partition(array, start, end) {
    var pivot = array[end];
    var pIndex = start;
    for(var i=start; i<end; i++) {
        if (array[i]<pivot) {
            swap(array, i, pIndex);
            pIndex++;
        }
    }
    swap(array, pIndex, end);
    return pIndex;
}

function swap(array, i, j) {
    var a = array[i];
    array[i]=array[j];
    array[j]=a;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Find the Median Python Solution

numbers = int(input())
num_array = input()
num_array = num_array.split(" ")
i = 0
temp = 0
while(i < numbers):
    num_array[i] = int(num_array[i])
    i += 1
num_array.sort()
if(len(num_array)%2 == 0):
    temp = len(num_array)/2
    ans = num_array[temp] + num_array[temp-1]
else:
    temp = int(len(num_array)/2)
    ans = num_array[temp]
print(ans)