Minimize Difference Between Sum of Squares in Array Permutation

You are provided with an array of size 8*N and you are provided a permutation of 8*N consecutive integers comprising of all the elements from ‘a’ to ‘a + 7*N ‘. Your task is to minimize the difference of the sum of the squares of the elements at even positions and the odd positions and print the permutation.

Examples:

Input : arr[]={ 1 , 2 , 3 , 4, 5 ,6 ,7 ,8 }
Output : 1 2 4 3 7 8 6 5 

The difference is 0 as - 
1 + 42 + 72 + 62 = 102 = 22 + 32 + 82 + 52

Input : arr[]={ 9 , 11 , 12 , 15 , 16 , 13 , 10 , 14}
Output : 9 10 12 11 15 16 14 13
The difference is 0
92 + 122+ 152 + 142 = 102 + 112 + 162 + 132 = 646

We can always arrange the elements such that the sum of the squares of the elements at even positions and the odd positions is the same and hence the difference to be zero.

The proof lies in the fact that ( S )² + ( S+3 )² – 4 = ( S+1 )² + ( S+2 )² .

So what we can do is that for the first set of 4 numbers we will keep the sum of squares of the elements in odd places higher than the sum in even places. That can be done by assigning ( S ) and ( S + 3 ) to the odd places and ( S+1 ) and ( S + 2 ) for the even places. Then for the next set of 4 consecutive integers, we will keep the sum in the even places higher than the odd places so that the previous loss is compensated. So for the set of 8 consecutive integers, we have balanced the sum, and since we have 8*N integers so we can also balance the sum for the rest of them by following the same approach.

Implementation:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int maximum(int arr[], int size)
{
    int ma = INT_MIN;
    for (int i = 0; i < size; i++)
    {
        ma = max(ma, arr[i]);
    }
    return ma;
}

int minimum(int arr[], int size)
{
    int mi = INT_MAX;
    for (int i = 0; i < size; i++)
    {
        mi = min(mi, arr[i]);
    }
    return mi;
}

void print_min(int arr[], int low, int high, int size)
{
    // Using the fact that:
    // s^2 + (s+3)^2 = (s+1)^2 + (s+2)^2 + 4.
    
    for (int i = 0; i < size; i += 4)
    {
        if (i % 8 == 0)
        {
            arr[i] = low;
            arr[i + 2] = low + 3;
            arr[i + 1] = low + 1;
            arr[i + 3] = low + 2;
            // Making the difference +4 for the even
        }
        else
        {
            arr[i] = low + 2;
            arr[i + 2] = low + 1;
            arr[i + 1] = low + 3;
            arr[i + 3] = low;
            // Making the difference -4 for the even
            // +4 - 4 = 0 hence it is balanced
        }
        low += 4;
    }

    // Printing the array
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int size = sizeof(arr) / sizeof(int);
    print_min(arr, minimum(arr, size), maximum(arr, size), size);
    return 0;
}

Output:

1 2 4 3 7 8 6 5