Given array arr find x,y such that the sum of the absolute differences of all the elements of the array to any one of x or y is minimum.

Requirement : Return the sum.

Example1 arr=[2,3,6,7] and 3,7 are chosen x,y.
|2-3| |3-3| |6-7| |7-7| = 2

Example2 arr=[1,3,5] and 1,4 are chosen x,y.
|1-1| |3-4| |5-4| = 2

My approach :

Assumption : In any integer array the average of all the present elements, upon subtracting from each element of the array and adding the difference gives the least sum.

I am sorting the array and trying to find an index which divides the array in 2 halves, so that the average of left half and the average of right half gives me x and y. Then finding the sum using x and y.

For any element to be considered in left_half : Math.abs(avg_left - arr[idx]) > Math.abs(avg_right - arr[idx]), where avg_left and avg_right both includes arr[idx]. And vice versa for right half. The solve function checks for every element to be incorporated in left/right half.

 public static boolean avg_diff(int[] arr, int idx) {
    int sum1 = 0, sum2 = 0;
    // finding sum from left and right both including idx element value
    for (int i = 0; i < arr.length; i  ) {
        if (i < idx)
            sum1  = arr[i];
        else if (i == idx) {
            sum1  = arr[i];
            sum2  = arr[i];
        } else
            sum2  = arr[i];
    }
    // finding the average in left and right half , both including idx element value
    int avg_left = sum1 / (idx   1);
    int avg_right = sum2 / (arr.length - idx);

    if (Math.abs(avg_left - arr[idx]) > Math.abs(avg_right - arr[idx])) {
        return true;
    }
    return false;
}

public static void solve(int[] arr) {
    Arrays.sort(arr);
    int i = arr.length - 1;
    while (i >= 0) {
        if (avg_diff(arr, i)) {
            i--;
        } else {
            // this is the partition index and is included in left half
            System.out.println("index : "   i   "   value : "   arr[i]);
            break;
        }
    }
}

Testcase : rr[] = {78,97,23,6,51,52,28,60,33,1,100}
My output : 165, expected output : 160

My approach is giving wrong answer in some test cases. I am new to programming. Please guide.

A.length() <= 5*10^3

CodePudding user response：

Your assumption is incorrect. To minimize the sum of the absolute differences you need to find the median, not the average. That's because as you move towards the median, more absolute differences are decreasing than increasing, so the sum of the absolute differences is decreasing.

Consider the following three numbers to see that it matters: [1, 2, 6]. The average is 3, the median is 2. If you pick x = 2 then the sum of the absolute differences is 5. If you pick x=3 then the sum of the absolute differences is 6.

CodePudding user response：

It is known problem if you should choose one number. It should be a median of array. Let the n be size of array. I guess, in this 2 need numbers is arr[n / 3] and arr[2 * n / 3].