Minimize the sum of squares of sum of N/2 paired formed by N numbers in C++

Problem statement

Given an array of n elements. The task is to create n/2 pairs in such a way that sum of squares of n/2 pairs is minimal.

Example

If given array is −

arr[] = {5, 10, 7, 4} then minimum sum of squares is 340 if we create pairs as (4, 10) and ( 5, 7)

Algorithm

1. Sort the array 2. Take two variables which point to start and end index of an array 3. Calulate sum as follows:    sum = arr[start] + arr[end];    sum = sum * sum; 4. Repeate this procedure till start < end and increment minSum as follows:    While (start < end) {       sum = arr[start] + arr[end];       sum = sum * sum;       minSum += sum;       ++start;       --end;    }

Example

#include <iostream> #include <algorithm> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; int getMinSquareSum(int *arr, int n) {    sort(arr, arr + n);    int minSum = 0;    int start = 0;    int end = n - 1;    while (start < end) {       int sum = arr[start] + arr[end];       sum *= sum;       minSum += sum;       ++start;       --end;    }    return minSum; } int main() {    int arr[] = {5, 10, 7, 4};    int res = getMinSquareSum(arr, SIZE(arr));    cout << "Minimum square sum: " << res << "\n";    return 0; }

Output

When you compile and execute above program. It generates following output −

Minimum square sum: 340