sum of each median on the array

Question

I am trying to get the sum of each median... and yes this is homework... my answer is wrong but I couldn't figure out why it's not giving me the correct answer. Any suggestion?

package coursera_week6_p2;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Coursera_week6_p2 {

public static void main(String[] args) throws FileNotFoundException {
    Scanner s = new Scanner(new File("/Users/michellepai/Downloads/Median.txt"));
    int[] array = new int[10000];
    int i = 0;
    while (s.hasNextLine()) {
        array[i] = Integer.parseInt(s.nextLine());
        i++;
    }
    Arrays.sort(array);

    int m = 0;
    long med = 0;
    for (int k = 0; k < array.length; k++) {
        if (k % 2 == 0) {
            m = k/2;
        } else {
            m =(k-1)/2;
        }
        System.out.println("arrayIndex [" + k + "]: "+ array[k] +" , median index: " + m +           " , median: " + array[m]);
        med = med + array[m];
        System.out.println("total: " + med);
        }
        System.out.println(med%10000);
    }
}

The goal of this problem is to implement the "Median Maintenance" algorithm (covered in the Week 5 lecture on heap applications). 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.

This is what I came out with... I finally got the answer right :D

public static void main(String[] args) throws FileNotFoundException {
    Scanner s = new Scanner(new File("/Users/michellepai/Downloads/Median.txt"));
    int[] array = new int[10000];
    int i = 0;
    while (s.hasNextLine()) {
        array[i] = Integer.parseInt(s.nextLine());
        i++;
    }
    int m = 0;
    long med = 0;
    for (int k = 0; k < array.length; k++) {
        //int k = 2;
        int temp[] = new int[k + 1];
        for (int j = 0; j <= k; j++) {
            temp[j] = array[j];
        }
        Arrays.sort(temp);
        if (k % 2 == 0) {
            m = k / 2;
        } else {
            m = (k - 1) / 2;
        }

        System.out.println("arrayIndex [" + k + "]: "+ array[k] +" , median index: " + m + " , median: " + array[m]);
        med = med + temp[m];
    }
    System.out.println(med % 10000);
}

Answer 1

I think the problem is here:

Letting xi denote the ith number of the file, the kth median mk is defined as the median of the numbers x1,…,xk

According to the definition above, mk is defined as the median of the numbers x1,…,xk. To compute mk, **you should sort x1,...,xk, but not the whole array. After you use Arrays.sort(array); to sort the whole array, then xk is not the ith number of the file.