Programming Geek
Rated 4.1/5 based on 446 reviews

Median Maintenance

The problem statement is taken from Coursera programming assignment #6 .

Download the text file here.

The goal of this problem is to implement the "Median Maintenance" algorithm . The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one. Letting xi denote the ith number of the file, the kth median mk is defined as the median of the numbers x1,,xk. (So, if k is odd, then mk is ((k+1)/2)th smallest number among x1,,xk; if k is even, then mk is the (k/2)th smallest number among x1,,xk.)

In the box below you should type the sum of these 10000 medians, modulo 10000 (i.e., only the last 4 digits). That is, you should compute (m1+m2+m3++m10000)mod10000.

Algorithm ( naive ):
  1. sum=0, input a[n]
  2. for each input a[i]
    1. Sort a[0..i]
    2. sum+=a[i/2]
  3. print sum%10000
JAVA implementation : 

import java.util.Arrays;
import java.util.Scanner;

public class MedianMaintenance {

    public static void main(String[] args) {
        int[] list = new int[10000];
        Scanner sc = new Scanner(;
        long sum = 0;

        for (int i = 0; i < list.length; i++) {

            list[i] = sc.nextInt();
            Arrays.sort(list, 0, i+1);