how to divide an integer array into 2 sub-arrays and make their averages equal?

Question

Please help me with the above question. An algorithm with a working example will be appreciated. Also, please handle the case when the above is not possible.

Okay, what I have till now is the following:

Go through entire array and get average of whole array. O(n). Let us call this avg

Then from this average can get the average of the whole array except a[0] (the formula is: avg(a[1..n-1])=(avg(a[0..n-1])*n-a[0])/(n-1)). Then you take this new average and compare it with a[0]. If they are not equal you move to the next value calculating the averages from the previously know averages using the formula from above.

Though someone has provided me a solution that "works", I am looking for the most efficient implementation.

Answer 1

A quick google search returned this. In any case, if you're not looking for performance, backtracking is always an option

EDIT: I tried to apply backtracking. My solution is in no way efficient. You can, of course, replace the average methods to avoid another level of cycling. Also, in order to show that there is no solution, you can just count the number the solutions.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class SOQuestion {

    /**
     * just prints a solution
     * 
     * @param list
     * @param indexes
     */
    public static void printSolution(List list, HashSet indexes) {
        Iterator iter = indexes.iterator();
        while (iter.hasNext()) {
            System.out.print(list.get((Integer) iter.next()) + " ");
        }
        System.out.println();
    }

    /**
     * calculates the average of a list, but only taking into account the values
     * of at the given indexes
     * 
     * @param list
     * @param indexes
     * @return
     */
    public static float avg(List list, HashSet indexes) {
        Iterator iter = indexes.iterator();
        float sum = 0;
        while (iter.hasNext()) {
            sum += (Integer) list.get((Integer) iter.next());
        }
        return sum / indexes.size();
    }

    /**
     * calculates the average of a list, ignoring the values of at the given
     * indexes
     * 
     * @param list
     * @param indexes
     * @return
     */
    public static float avg_e(List list, HashSet indexes) {
        float sum = 0;
        for (int i = 0; i < list.size(); i++) {
            if (!indexes.contains(i)) {
                sum += (Integer) list.get(i);
            }
        }
        return sum / (list.size() - indexes.size());
    }

    public static void backtrack(List list, int start, HashSet indexes) {
        for (int i = start; i < list.size(); i++) {
            indexes.add(i);
            if (avg(list, indexes) == avg_e(list, indexes)) {
                System.out.println("Solution found!");
                printSolution(list, indexes);
            }
            backtrack(list, i + 1, indexes);
            indexes.remove(i);
        }
    }

    public static void main(String[] args) {
        List test = new ArrayList();
        test.add(2);
        test.add(1);
        test.add(3);

        backtrack(test, 0, new HashSet());
    }
}