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
3
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)
Other Solutions
