Return a subset of integers that maximizes its (mean - median)

Question

A set of integers is given as input .You have to return subset of that set so that value of mean - median is maximum for that subset.

Example 1

Input

{1,2,3,4} 

Output

{1,2,4}

Example 2

Input

{1,2,2,3,3}

Output

{2,2,3}

Solution 1

package subsetMean_Median;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MySolution {
    public static void main(String[] args) {
        int[] arr= 
            {2,3,2,1,3};
//          {1,3,2,4};
        Arrays.sort(arr);
        int[] outp=meanMedian(arr);
        for(int e:outp) {
            System.out.print(e+"\t");
        }
    }

    protected static int[] meanMedian(int[] arr) {
        double median=findMedian(arr);
        double mean=findMean(arr);
        double diff=median-mean;
        int MAXINDEX=0;
        int n=arr.length;
        double sets=(1<<n);
        System.out.println("sets:"+sets);
        for(int i=1;i<=sets;i++) {
            int[] subset=findSubset(i,arr);
            mean=findMean(subset);
            median=findMedian(subset);
            if(mean -median>diff) {
                diff=mean-median;MAXINDEX=i;
            }
        }
        System.out.println("mean: "+mean+"\tmedian: "+median+"\tdiff: "+diff);
        return findSubset(MAXINDEX,arr);
    }
    protected static int[] findSubset(int counter, int[] arr) {
        int n=arr.length;
        List<Integer> ls=new ArrayList<Integer>();
        for(int j=0;j<n;j++) {
            if((counter & (1<<j))>0) {
                ls.add(arr[j]);
            }
        }
        int[] output= new int[ls.size()];
        for(int j=0;j<ls.size();j++) {
            output[j]=ls.get(j);
        }
        return output;
    }

    protected static double findMean(int[] arr) {
        int n=arr.length;
        double sum=0;
        if(n==0) return 0;
        for(int i=0;i<n;i++)
            sum +=arr[i];
        return (sum/n);
    }

    protected static double findMedian(int[] arr) {
        int n=arr.length;
        if(n%2==1)
            return arr[(n/2)];
        else if(n>=2)
            return 0.5*(arr[((n-2)/2)]+arr[n/2]);
        else return 0;
    }
}

Solution 2

For every possible median:

lllllmrrrrr

Sort both parts L and R, then start choosing in pair lr maximal elements from both parts and with addition of every next element recompute mean, store arrangement with the best difference. Then the same for minimal elements.

There are about N possible medians, sorting takes O(N*lgN), on every iteration you need to compute up to N means, you can do it in O(N). So, overall complexity is O(N^3*LgN), but most likely you can avoid sorting on every iteration, instead sort whole array only once and update parts in O(1) on every iteration. With such an improvements it is O(N^2).

Solution 3

The most important thing in this problem is to find the Subset.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
    
public class MeanMedian {
    public static void main(String[] args) {

        int[] arr = { 1, 2, 3 };// { 1, 2, 2, 3, 3 };// { 1, 2, 3, 4 };

        returnMaxMeanMedian(arr);

    }

    private static void returnMaxMeanMedian(int[] arr) {
        double max = -999.9;

        List<Integer[]> subArr = subSet(arr);

        Integer[] maxArr = new Integer[1];

        for (Integer[] sub : subArr) {

            double newMax = calcDiff(sub);

            if (max <= newMax) {
                max = newMax;
                maxArr = sub;
            }
        }
        System.out.println(Arrays.toString(maxArr));
    }

    private static double calcDiff(Integer[] sub) {
        // calc. mean
        double sum = 0;
        for (int i = 0; i < sub.length; i++) {
            sum += sub[i];
        }
        sum = sum / sub.length;

        // calc. median
        double median = 0;
        if (sub.length % 2 == 0)
            median = (double) (sub[(sub.length / 2) - 1] + sub[sub.length / 2]) / 2;
        else
            median = sub[sub.length / 2];

        double diff = sum - median;
        return diff;
    }

    private static List<Integer[]> subSet(int[] arr) {
        List<Integer[]> subArr = new ArrayList<Integer[]>();

        int n = arr.length;

        // Run a loop until 2^n
        // subsets one by one
        for (int i = 0; i < (1 << n); i++) {

            String subSet = "";
            // Print current subset
            for (int j = 0; j < n; j++)

                if ((i & (1 << j)) > 0)
                    subSet += arr[j] + " ";

            subArr.add(convertToInt(subSet.trim().split(" ")));
        }
        return subArr;
    }

    private static Integer[] convertToInt(String[] arr) {

        if (arr[0] == "")
            return new Integer[] { 0 };

        Integer[] intArr = new Integer[arr.length];

        for (int i = 0; i < arr.length; i++) {
            intArr[i] = Integer.parseInt(arr[i].trim());
        }

        return intArr;
    }
}

Comments

[Paul Hankin]

There are about N^2/2 + N medians -- one for each element in the list, and one for each pair of elements.

[Shekhar Rai]

Please add some details as well

[Bhaskar13]

What details are you looking for?

[Bhaskar13]

It is going through all subsets

[Shekhar Rai]

It's good practice to provide some details to satisfy your code. Putting only code may not be clear for the viewers unless they ran your code or go through your code line by line. You can go through this link write good answers for more detail.

[Vikash]

@Bhaskar13 (or someone else) Can you explain logic in findSubset method?

[Bhaskar13]

geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java

[javaGroup456]

the line where left shift operator is used sets=(1<<n); is basically calculating the total number of subsets possible for an array of length n. the value of variable sets would be equal to 2 raised to the power n.

[javaGroup456]

@Bhaskar13 this solution i working. but the complexity would be order of 2 to power n , which is quite high ( actually n * 2 to power n as we are calculating mean every single time) . Can you point how to optimize this solution.

[javaGroup456]

Could you please elaborate bit more.

[Null]

Please edit your post to explain how it answers the question.