Arrange array so adjacent has less space that gives minimum 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;
}

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.