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;
}
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;
}
The OP states that in the first step any two elements can be removed from the array. If that is the case, thereafter the problem is equal to finding a maximum weighted matching in a graph. See e.g. this explanation.
Implementations for algorithms for this problem can be found here (with a good explanation of the problem itself) in Boost (C++). In Java, which the OP is after, several algorithms can be found here, in the JGraphT library.
Note that usually the algorithms are written for a maximum weight, whereas the OP is after a minimum weight. The strategy to cast the graph in this form is to:
To illustrate, in the original example, after removal of 100 and 200, the following elements remain in the array: 1,3,4,6,3,4. Each element represents an edge (say A, B, C, D, E, F). The vertex A-B has weight -2, the vertex A-C has weight -3, and so on. If we apply an algorithm to find a maximum matching with maximum weight in this graph, it will correspond to a minimum weight in the OP's problem.
I tested the previous posted solution for various other inputs but it was not valid for different sets of inputs. Hence , I am posting a different approach that is working fine for different sets of inputs.
Sort the array in ascending order
Take a variable to initialize the minimum sum to the sum of difference of the last two and first two elements of the array.
Start a loop (with initially excluding the last two elements of array).
Each run of loop should calculate the sum of difference of pairs and compare it with minimum sum to update its value if the current run of loop has the minimum total.
Hence , we will be covering all the pairs after we finish with the execution of loop and will get the minimum sum .
public static int findMinSum(int[] a){
Arrays.sort(a);
int minSum=a[1]-a[0]+a[a.length-1]-a[a.length-2];
for (int i=0,j=a.length-2;i<a.length/2 && j<a.length;i++,j++){
int sum=0;
int counter=i;
while(counter<j){
sum=sum+(a[counter+1]-a[counter]);
counter+=2;
}
if(sum < minSum){
minSum=sum;
}
}
return minSum;
}
- original array={95,98,100,101,102,110}
- initialize minimum sum to (110-102)+(98-95) = 11
- loop stages :
- (98-95) +(101-100) = 4 (new minimum sum=4)
- (100-98)+(102-101) = 3 (new minimum sum=3)
- (101-100)+(110-102) = 9 (minimum sum remains 3)
I have further tested the following set of inputs :-
{1,3,3,4,4,6,100,200}
{1,50,51,60}
{1,2,100,200,400,401}
{1,2,100,300,400,401}
{1,2,3,4,4,6,100,200}
{95,98,100,101,102,401}
Please do inform if any descrepancies occur for any input sets.