Arrange array so adjacent has less space that gives minimum sum

user_3181365 0
Viewed 949

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;
}
algorithm java
4 Answers

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

Simple block code for understanding

enter image description here

Java Code

package com.company;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
    // write your code here
        System.out.println(MinSumDiff(new int[] {1,2,3,4,4,6,100,200}));
    }

    private static int MinSumDiff(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        if(!(0==(n%2))){
            System.exit(2);// '2' refers not divisible by 2
        }
        int sum0 = 0,
            sum1 = arr[n-1] - arr[0] + 1,//LAST ITEM OF ARRAY(LARGEST) - FIRST(SMALLEST) ITEM
            sum2 = sum1;
        int dispo0 = -1,
            dispo1 = -1,
            dispo2 = -1;

        for (int i=0;i<n;i++){
            int sum0_old = sum0;//SET OLD TO CURRENT BECAUSE CURRENT(SUM0) WILL CHANGE LATER, WE CAN USE THIS FOR VERIFICATION
            int sum1_old = sum1;//SET OLD TO CURRENT BECAUSE CURRENT(SUM1) WILL CHANGE LATER, WE CAN USE THIS FOR VERIFICATION
            //------------------------------------------------------------
            if (dispo0 == -1) {
                dispo0 = i;//SET CURENT `I` FOR USE FOR NEXT TIME'S PREVIOUS ...[1]
            } else {
                sum0 += arr[i] - arr[dispo0];//CURRENT ITEM - PREVIOUS ITEM(PREVIOUS FROM [1])
                dispo0 = -1;//REPEAT 
            }
            //------------------------------------------------------------
            if (dispo1 == -1) {
                dispo1 = i;//SET CURENT `I` FOR USE FOR NEXT TIME'S PREVIOUS ...[2]
            } else {
                int add = arr[i] - arr[dispo1];//CURRENT ITEM - PREVIOUS ITEM(PREVIOUS FROM [2])
                if (sum0_old < sum1 + add) {
                    sum1 = sum0_old;//IF `SUM0(OLD)` IS LESS THAN `SUM1` THEN WHY DO YOU AVOID IT,SO SET `SUM1` TO `SUM0(OLD)`
                    dispo1 = i;//SETS `I` NOT AS -1 BECAUSE IT WANTS TO DO THIS AGAIN AND CHECK
                } else {
                    sum1 += add;//IF ADDING THE VARIABLE `ADD` WILL BE LESS THAN SUM0(OLD) THEN YOU CAN ADD IT TO `SUM1` NOW
                    dispo1 = -1;//REPEAT 
                }
            }
            //------------------------------------------------------------
            if (dispo2 == -1) {
                dispo2 = i;//SET CURENT `I` FOR USE FOR NEXT TIME'S PREVIOUS ...[3]
            } else {
                sum2 += arr[i] - arr[dispo2];//CURRENT ITEM - PREVIOUS ITEM(PREVIOUS FROM [3]) ...4
                dispo2 = -1;//REPEAT 
            }
            //------------------------------------------------------------
            if (sum2 > sum1_old) {
                sum2 = sum1_old;//IF `SUM1(OLD)` IS LESS THAN `SUM2` THEN WHY DO YOU AVOID IT,SO SET `SUM2` TO `SUM1(OLD)`
                dispo2 = i;//EVEN THOUGH `DISPO2` IS -1 IT SETS TO `I` BECAUSE OF ABOVE CODE EXECUTION (WHICH IS USEFUL FOR [4])
            }
            //------------------------------------------------------------
        }
        return sum2;//RETURN THE FINAL RESULT THAT'S STORED IN LAST VARIABLE SUM2!!!
    }
}

P.S

The idea is from @danien's answer

I have convert it to block code&java code with explained comments

user_148628850

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.

Approach:-

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

Example:-

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

user_163930020

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:

  • Create a graph where each element of the array is a vertex
  • Each edge (connection between each vertex) has a weight equal to the absolute difference between the value of both vertices, multiplied by -1

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.

user_107212630
Related