I have an array of numbers with even size, here is my task:

a) Discard any 2 elements from the array. b) Then pair the elements and calculate the sum of differences between the elements in the pair such that the sum is minimum.

Example:

array size even say 8.
array elements : 1,3,4,6,3,4,100,200

Ans:
5

Explanation:

Here I will remove 100 and 200, as pairing them gives me a difference of (200 - 100) = 100. So remaining elements are [1,3,4,6,3,4] Pairs with minimum sum are : (1 3) , (4 3), (6 4). = |3-1| = 2, |4-3|=1,|6-4| = 2. So Sum = 2 1 2 = 5

Example:

array size even say 4.
array elements : 1,50,51,60

Ans:
1

Explanation: Here I will remove 1 and 60 so I will get the minimum sum. So the remaining elements are [50, 51], same as the adjacent [50 51] = 1. My code will fail for this case and returns 49.

How to achieve this in java?

I tried sorting the elements like this but this is not the correct approach for all kinds of inputs.

public static int process(int[] a) {
   int n = a.length;
   int n1 = n/2-1;
   Arrays.sort(arr);
   int sum = 0;
   for(int i=0; i<n1*2; i =2) {
     sum  = a[i 1] - a[i];
   }
   return sum;
}

CodePudding user response：

In this kind of problem, the real issue is to find a good algorithm.
this post will insists on this aspect. A C code is provided at the end just to illustrate it.

It is clear we must begin by sorting the array.
A solution consists in iteratively calculate three sums, where

sum0 is the minimum sum assuming no element has been removed
sum1 is the minimum sum assuming one element has been removed
sum2 is the minimum sum assuming two elements has been removed

During this process, the code must keep trace of the last element available to calculate a difference, one for each sum (i_dispo0, i_dispo1, i_dispo2).

Principles:

- if sum1 > sum0: sum1 is replaced by sum0
- if sum2 > sum1: sum2 is replaced by sum1

Complexity: O(n logn)for sorting, O(n) for the optimization phase.

Code:

The algorithm is illustrated by the following simple code in C .
It should be easy to understand.

Output: 5 1 2 0 2

#include <iostream>
#include <vector>
#include <algorithm>

int min_sum_diff (std::vector<int>& arr) {
    int n = arr.size();
    if (n%2) exit (1);
    std::sort (arr.begin(), arr.end());
    int sum0 = 0, sum1 = arr[n-1] - arr[0]   1, sum2 = arr[n-1] - arr[0]   1;
    int i_dispo0 = -1, i_dispo1 = -1, i_dispo2 = -1;
    for (int i = 0; i < n;   i) {
        int sum0_old = sum0;
        int sum1_old = sum1;
        if (i_dispo0 == -1) {
            i_dispo0 = i;
        } else {
            sum0  = arr[i] - arr[i_dispo0];
            i_dispo0 = -1;
        }
        if (i_dispo1 == -1) {
            i_dispo1 = i;
        } else {
            int add = arr[i] - arr[i_dispo1];
            if (sum0_old < sum1   add) {
                sum1 = sum0_old;
                i_dispo1 = i;
            } else {
                sum1  = add;
                i_dispo1 = -1;
            }
        }
        if (i_dispo2 == -1) {
            i_dispo2 = i;
        } else {
            sum2  = arr[i] - arr[i_dispo2];
            i_dispo2 = -1;
        }
        
        if (sum2 > sum1_old) {
            sum2 = sum1_old;
            i_dispo2 = i;
        }
        //std::cout << i << " : " << sum0 << "  " << sum1 << "  " << sum2 << '\n';
    }
    return sum2;
}

int main() {
    std::vector<std::vector<int>> examples = {
        {1, 3, 4, 6, 3, 4, 100, 200},   // -> 5
        {1, 50, 51, 60},                // -> 1
        {1,2,100,200,400,401},          // -> 2
        {1, 10, 10, 20, 30, 30},        // -> 0
        {1, 10, 11, 20, 30, 31}         // -> 2
    };
    for (std::vector<int>& arr: examples) {
        int sum = min_sum_diff (arr);
        std::cout << sum << '\n';
    }
    return 0;
}

CodePudding user response：

I think you could follow the steps:

1. To minimize a sum, we have to minimize each summand;
2. To minimize a summand, we have to select two numbers as much as closer to each other (i.e. we have 0 when selecting two same numbers).

public static int process(int[] arr) {
    assert arr.length % 2 == 0 : "Expected an even length array";

    Map<Integer, Integer> map = histogram(arr);
    removePairs(map);

    int sum = 0;

    for (int sub = 1; getTotalNumbers(map) > 2; sub  ) {
        for (int a : new HashSet<>(map.keySet())) {
            int b = a   sub;

            if (map.getOrDefault(a, 0) == 0)
                continue;
            if (map.getOrDefault(b, 0) == 0)
                continue;

            map.put(a, map.get(a) - 1);
            map.put(b, map.get(b) - 1);
            sum  = sub;
        }
    }

    return sum;
}

private static Map<Integer, Integer> histogram(int[] arr) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int a : arr)
        map.put(a, map.getOrDefault(a, 0)   1);

    return map;
}

private static void removePairs(Map<Integer, Integer> map) {
    for (int a : new HashSet<>(map.keySet())) {
        int count = map.remove(a) % 2;

        if (count != 0)
            map.put(a, count);
    }
}

private static int getTotalNumbers(Map<Integer, Integer> map) {
    return map.values().stream().mapToInt(i -> i).sum();
}

process(new int[] { 1, 3, 4, 6, 3, 4, 100, 200 });  // 5
process(new int[] { 1, 50, 51, 60 });               // 1
process(new int[] { 1, 2, 100, 200, 400, 401 }));   // 2
process(new int[] { 1, 10, 10, 20, 30, 30 });       // 0
process(new int[] { 1, 10, 11, 20, 30, 31 });       // 2