Sorting: Given an array, minimize sum of product of consecutive pairs

Problem Statement:

You are given an array.

You need to re arrange an array in such a way that, when multiply an element with its alternative element and add the resultant elements should return the min sum.

Example:

Input:
[3, 6, 2, 8, 5, 0, 1 0]

Output: 11

If we arrange the elements in [8 0 6 0 5 1 3 2]

Solution Explanation:

Sort the array.

Create 2 array, even and odd.

Then push half of the elements into even array and another half into odd array.

Sort even array in descending order and odd into ascending order.

Now arrange even and odd array elements and return the result,

Time Complexity: O(nlogn)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


using namespace std;

int solution(int arr[], int n)
{
    vector<int> evenArr;
    vector<int> oddArr;

    sort(arr, arr+n );

    for (int i = 0; i < n; i++)
    {
        if (i < n/2)
            oddArr.push_back(arr[i]);
        else
            evenArr.push_back(arr[i]);
    }

    sort(evenArr.begin(), evenArr.end(), greater<int>());

    int i = 0, sum = 0;
    
    for (int j=0; j<evenArr.size(); j++)
    {
        arr[i++] = evenArr[j];
        arr[i++] = oddArr[j];
        sum += evenArr[j] * oddArr[j];
    }

    return sum;
}

int main()
{
    int arr[] = { 3, 6, 2, 8, 5, 0, 1, 0 };
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout << "Result = " << solution(arr, n);

    cout << "\nArray : ";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
    
    return 0;
}

Output

Result = 11
Array : 8 0 6 0 5 1 3 2