6

A set of integers is given as input. You have to return the subset of that set so that the 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}
4
  • Try to format your question for better readability.
    – Wils
    Apr 18, 2018 at 6:58
  • 1
    What is "mean - median" - special term? Difference of these values?
    – MBo
    Apr 18, 2018 at 7:12
  • @MBo Judging from the examples provided, I would assume it's the result of subtracting the median from the mean. But what about a subset with an even number of elements? Is the median in this case the average of the two central elements?
    – r3mainer
    Apr 18, 2018 at 7:50
  • yes . mean - median means difference in their values. in case of even number of elements , median would be average of two middle elements . Apr 19, 2018 at 6:53

9 Answers 9

2
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;
    }
}


8
  • 3
    Please add some details as well Dec 18, 2019 at 9:27
  • What details are you looking for?
    – Bhaskar13
    Dec 20, 2019 at 18:56
  • It is going through all subsets
    – Bhaskar13
    Dec 20, 2019 at 18:56
  • 1
    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. Dec 21, 2019 at 3:16
  • @Bhaskar13 (or someone else) Can you explain logic in findSubset method?
    – Vikash
    Jul 2, 2020 at 11:36
1

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).

1
  • There are about N^2/2 + N medians -- one for each element in the list, and one for each pair of elements. Apr 19, 2018 at 15:07
1

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;
    }
}
0

Sort the list in O(n log n).

Deleting any element to the left of the median (center element or pair) has the same effect on the median, but affect the mean differently. Ditto for elements to the right.

That means that if anything will improve (mean - median), one of these will improve it the most:

  1. the smallest element in the array
  2. the smallest element to the right of the median
  3. one of the element(s) that comprises the median

I.e., for each possible new median, how can we achieve the largest mean?

Repeatedly check these 3-4 for improving mean-median, deleting whatever improves the most. Each operation is O(1), as is recalculating the mean and median. You have to do this at most O(n) times.

The running time is O(n log n) if the list is unsorted, otherwise O(n).

1
  • Could you please elaborate bit more. Aug 5, 2020 at 17:19
0

Is this question only for a positive sequence of numbers? If yes, there's this efficient piece of code I wrote:

import java.util.Scanner;

public class MeanMedian {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner sc = new Scanner(System.in);
    int i;
    int j;
    int k;
    int in_length;
    int mid_loc;
    int sum_arr;
    float median = 0.0f;
    float mean = 0.0f;
    float delta = 0.0f;
    float incremental_delta = 0.0f;
    float MEDIAN_FOR_MAX_DELTA = 0.0f;
    float MEAN_FOR_MAX_DELTA = 0.0f;
    float MAX_DELTA = -1.0f;
    int MAX_SEQ_LENGTH = 0;

    System.out.print("Enter the length of input: ");
    in_length = sc.nextInt(); 

    int in_arr[]= new int [in_length+1];
    int out_arr[] = new int [in_length+1]; //This is the maximum size of the output array.
    int MAX_DELTA_ARR[] = new int [in_length+1];


    // STAGE-1: Accept the input sequence    
    for (i = 1; i <= in_length; i++) {
     System.out.print("Enter the input #" + i + ": ");
     in_arr[i] = sc.nextInt();
    }
    // STAGE-1 completed.


    // STAGE-2: Sort the array (Bubble sort in Ascending order)
    for (j = 1; j < in_length; j++) {
        for (i = in_length; i > j; i--) {
            if (in_arr[i-1] > in_arr[i]) {
                k = in_arr[i];
                in_arr[i] = in_arr[i-1];
                in_arr[i-1] = k;
            }
        }
    }
    // STAGE-2 completed.


    // STAGE-3: Compute Max Delta
    MAX_DELTA = -99999; //Store as large -ve number as float data type can hold.

    for (i = in_length; i > 2; i--) {
        // STAGE-3a: Optional - Clear the out_arr[]
        for (j = 1; j <= in_length; j++) {
            out_arr [j] = 0;
        }
        // STAGE-3a completed.


        // STAGE-3b: Determine the index of the median for the sequence of length i
        if (i % 2 == 1) {
            mid_loc = (i + 1)/2;
        }
        else {
            mid_loc = (i / 2) + 1;
        }
        // STAGE-3b completed.


        // STAGE-3c: Create the selection that gives the min median and max mean.
        // STAGE-3c1: Create left side of mid point.
        for (j = mid_loc; j > 0; j--) {
            out_arr[j] = in_arr[j];
        }
        // STAGE-3c1 completed.


        // STAGE-3c2: Create right side of mid point.
        k = in_length;
        for (j = i; j > mid_loc; j--) {             
            out_arr[j] = in_arr[k];
            k = k - 1;
        }
        // STAGE-3c2 completed.


        // STAGE-3c3: Do the SHIFT TEST.
        //for (; k <=  mid_loc + in_length - i; k++) {
        for (k = mid_loc + 1; k <=  mid_loc + in_length - i; k++) {
            if (i % 2 == 1) {
                incremental_delta = ((float)in_arr[k] - (float)out_arr[1])/i - ((float)in_arr[k] - (float)out_arr[mid_loc]);
            }
            else {
                incremental_delta = ((float)in_arr[k] - (float)out_arr[1])/i - (((float)in_arr[k] - (float)out_arr[mid_loc]/2));
            }
            if (incremental_delta >= 0 ) {
                //Insert this new element
                for(j = 1; j < mid_loc; j++) {
                    out_arr[j] = out_arr[j+1];
                }
                out_arr[mid_loc] = in_arr[k];
            }
        }
        // STAGE-3c3 completed. 


        // STAGE-3d: Find the median of the present sequence.
        if(i % 2 == 1) {
            median = out_arr[mid_loc];
        }
        else {
            median = ((float)out_arr[mid_loc] + (float)out_arr[mid_loc - 1])/2;
        }
        // STAGE-3d completed. 


        // STAGE-3e: Find the mean of the present sequence.
        sum_arr = 0;
        for(j=1; j <= i ; j++) {
            sum_arr = sum_arr + out_arr[j];
        }
        mean = (float)sum_arr / i;
        // STAGE-3e completed. 


        // STAGE-3f: Find the delta for the present sequence and compare with previous MAX_DELTA. Store the result.
        delta = mean - median;

        if(delta > MAX_DELTA) {
            MAX_DELTA = delta;
            MEAN_FOR_MAX_DELTA = mean;
            MEDIAN_FOR_MAX_DELTA = median;
            MAX_SEQ_LENGTH = i;
            for (j = 1; j <= MAX_SEQ_LENGTH; j++) {
                MAX_DELTA_ARR[j] = out_arr[j];
            }
        }
        // STAGE-3f completed.  
    }


    // STAGE-4: Print the result.
    System.out.println("--- RESULT ---");
    System.out.print("The given input sequence is: ");
    System.out.print("{ ");
    for(i=1; i <= in_length; i++) {
        System.out.print(in_arr[i]);
        System.out.print(" ");
    }

    System.out.print("}");
    System.out.println("");
    System.out.print("The sequence with maximum difference between mean and median is: ");
    System.out.print("{ ");
    for(i=1; i <= MAX_SEQ_LENGTH; i++) {
        System.out.print(MAX_DELTA_ARR[i]);
        System.out.print(" ");
    }

    System.out.print("}");
    System.out.println("");
    System.out.println("The mean for this sequence is: " + MEAN_FOR_MAX_DELTA);
    System.out.println("The median for this sequence is: " + MEDIAN_FOR_MAX_DELTA);
    System.out.println("The maximum difference between mean and median for this sequence is: " + MAX_DELTA);

}

}

This code has order O(n) (if we ignore the necessity to sort the input array).

In case, -ve inputs are also expected - the only way out is by evaluating each subset. The downside to this approach is that the algorithm has exponential order: O(2^n).

As a compromise you could use both types of algorithm in your code and switch between the two by evaluating the input sequence. By the way, where did you come across this question?

0
from itertools import combinations

[Verfication of the code][1]
# function to generate all subsets possible, there will be 2^n - 1 subsets(combinations)
def subsets(arr):
    temp = []
    for i in range(1, len(arr)+1):
        comb = combinations(arr, i)
        for j in comb:
            temp.append(j)
    return temp

# function to calculate median
def median(arr):
    mid = len(arr)//2
    if(len(arr)%2==0):
        median = (arr[mid] + arr[mid-1])/2
    else:`
        median = arr[mid]
    return median

# function to calculate median
def mean(arr):
    temp = 0
    for i in arr:
        temp = temp + i
    return temp/len(arr)

# function to solve given problem
def meanMedian(arr):
    sets = subsets(arr)
    max_value = 0
    for i in sets:
        mean_median = mean(i)-median(i)
        if(mean_median>max_value):
            max_value = mean_median
            needed_set = i
    return needed_set



  [1]: https://i.stack.imgur.com/Mx4pc.png
0

So I tried a little on the problem and here is a code that might help you. Its written in a way that should be easy to read, and if not, do let me know. Maybe you need to take array input from the user as I have taken a fixed array. That shouldn't be much of a problem I am sure.

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

class MeanMinusMedian 
{
    private static float mean = 0;
    private static float median = 0;
    private static float meanMinusMedian = 0;
    private static List<Integer> meanMinusMedianList = null;

    private static void formMeanMinusMedianArr(int data[], int sumOfData) 
    {
        findMean(data, sumOfData);
        findMedian(data);
        if ((mean - median) > meanMinusMedian) {
            meanMinusMedian = mean - median;
            meanMinusMedianList = new ArrayList<Integer>();
            Arrays.stream(data) 
            .forEach(e->meanMinusMedianList.add(e));
        }
    }

/**
 * @param data
 */
private static void findMedian(int[] data) {
    int dataLen = data.length;
    median = data.length % 2 == 0 ? ((float)data[dataLen / 2] + (float)data[dataLen / 2 - 1]) / 2 : data[dataLen / 2];
}

/**
 * @param data
 * @param sumOfData
 */
private static void findMean(int[] data, int sumOfData) {
    mean = ((float)sumOfData /(float) data.length);
}

/**
 * 
 * @param arr
 * @param data
 * @param start
 * @param end
 * @param index
 * @param runningVal
 */
private static void combinationUtil(int arr[], int data[], int start, int end, int index, int runningVal) {
    // Current combination is ready to be printed, print it
    if (index == runningVal) {
        formMeanMinusMedianArr(data, Arrays.stream(data) // Step 1 
                  .sum());
        return;
    }
    // replace index with all possible elements. The condition
    // "end-i+1 >= r-index" makes sure that including one element
    // at index will make a combination with remaining elements
    // at remaining positions
    for (int i = start; i <= end && end - i + 1 >= runningVal - index; i++) {
        data[index] = arr[i];
        combinationUtil(arr, data, i + 1, end, index + 1, runningVal);
    }
}

/**
 * 
 * @param arr
 * @param n
 * @param runningVal
 */
private static void printCombination(int arr[], int n, int runningVal) {
    int data[] = new int[runningVal];
    // Print all combination using temporary array 'data[]'
    combinationUtil(arr, data, 0, n - 1, 0, runningVal);
}

public static void main(String[] args) {
    int arr[] = { 1, 2, 2, 3, 3 };
    int runningVal = 1;//Running value
    int len = arr.length;
    for (int i = 1; i < arr.length; i++) {
        printCombination(arr, len, runningVal + i);
    }
    System.out.println(meanMinusMedianList);
}

}

0

Taking reference of answer of Bhaskar13 https://stackoverflow.com/a/59386801/3509609 , I solved it without using the bit shift operators, to add more readability.

package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class MeanMinusMedianMax {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxDiffrenceSubSet(4, new int[] { 4, 2, 3, 1 })));
        System.out.println(Arrays.toString(maxDiffrenceSubSet(4, new int[] { 1, 2, 2, 3, 3 })));
    }

    public static int[] maxDiffrenceSubSet(int n, int[] input2) {

        int totalSubsets = (int) Math.pow(2, n);
        Map<Integer, ArrayList<Integer>> subsetsMap = new HashMap<Integer, ArrayList<Integer>>();
        Integer maxKey = null;
        double maxDiff = 0;

        for (int i = 0; i < totalSubsets; i++) {
            String binaryString = Integer.toBinaryString(i);
            while (binaryString.length() < 4) {
                binaryString = "0" + binaryString;
            }
            char[] currentPick = binaryString.toCharArray();
            ArrayList<Integer> currentList = new ArrayList<Integer>();
            for (int x = 0; x < currentPick.length; x++) {
                if ((currentPick[x]) == '1') {
                    currentList.add(input2[x]);
                }
            }
            Collections.sort(currentList);
            subsetsMap.put(i, currentList);
            double mean = findMean(currentList);
            double median = findMedian(currentList);
            double currentDifference = mean - median;
            if (currentDifference > maxDiff) {
                maxDiff = currentDifference;
                maxKey = i;
            }
        }

        return subsetsMap.get(maxKey).stream().mapToInt(i -> i).toArray();
    }

    static double findMean(ArrayList<Integer> arr) {

        int n = arr.size();
        double sum = 0;
        if (n == 0)
            return 0;
        for (int i = 0; i < n; i++)
            sum += arr.get(i);
        return (sum / n);
    }

    static double findMedian(ArrayList<Integer> arr) {
        int n = arr.size();
        if (n % 2 == 1)
            return arr.get((n / 2));
        else if (n >= 2)
            return 0.5 * (arr.get(((n - 2) / 2)) + arr.get(n / 2));
        else
            return 0;
    }
}
0
class UserMainCode (object):
    def meanmedian(cls,ip1,ip2=[]):
        s = []
        s = ip2
        lst = []
        final = []
        op = []
        max_val = 0
        diff  = 0
        for i in range(1,ip1+1):
            n=i
            lst = list(itertools.combinations(s,n))
            final = final +lst      
        for i in range(len(final)):
            men = statistics.mean(final[i])
            med = statistics.median(final[i])
            diff = men - med
            if max_val < diff:
                op = final[i]
                max_val = diff
        return op
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.