Rearrange an array so that the sum of the products of consecutive pairs of elements is minimal, written in C++

We have an array of positive integer type, assuming it is arr[], with any size. The task is to rearrange the array such that when we multiply an element with its adjacent elements and then add all the resulting elements, the smallest sum is returned.

Let us look at different input and output situations:

Input - int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}

Output - Rearrange the array to minimize the sum, that is, the product of a consecutive pair of elements is: 7 0 5 0 5 1 2 1

Explanation - We have an integer array of size 8. Now we will rearrange the array i.e. 7 0 5 0 5 1 2 1. We will check if the minimum sum is returned, i.e. 7 * 0 5 * 0 5 * 1 2 * 1 = 0 0 5 2 = 7.

Input - int arr[] = {1, 3, 7, 2, 4, 3}

Output - Rearrange the array to Minimizing the sum, i.e. the product of a consecutive pair of elements is: 7 1 4 2 3 3

Explanation - We have an integer array of size 6. Now we will rearrange the array i.e. 7 1 4 2 3 3. We will check if the minimum sum is returned, which is 7 * 1 4 * 2 3 * 3 = 7 8 9 = 24.

The method used in the following program is as follows:

• Input an array of integer type and calculate the size of the array.

• Sort the array using the sort method of C STL, passing the array and the size of the array to the sort function.

• Declare an integer variable and set it to the return value of the calling function.

Rearrange_min_sum(arr, size)

Inside the function Rearrange_min_sum(arr, size)

• Create a variable, let's say, 'even' and 'odd' type of type vector which stores integer variables.

• Declare a variable as temp and total and initialise it with 0.

• Start loop FOR from i to 0 till i less than size. Inside the loop, check IF i is less than size/2 then push arr[i] to odd vector ELSE, push arr[i] to even vector

• Call the sort method by passing even.begin(), even.end() and greater().

• Start loop FOR from i to 0 till i less than even.size(). Inside the loop, set arr[temp ] to even[j], arr[temp ] to odd[j] and total to total even[j] * odd[j]

• Return total

Print the result.

Example

#include <bits/stdc++.h>
using namespace std;
int Rearrange_min_sum(int arr[], int size){
   vector<int> even, odd;
   int temp = 0;
   int total = 0;
   for(int i = 0; i < size; i++){
      if (i < size/2){
         odd.push_back(arr[i]);
      }
      else{
         even.push_back(arr[i]);
      }
   }
   sort(even.begin(), even.end(), greater<int>());
   for(int j = 0; j < even.size(); j++){
      arr[temp++] = even[j];
      arr[temp++] = odd[j];
      total += even[j] * odd[j];
   }
   return total;
}
int main(){
   int arr[] = { 2, 5, 1, 7, 5, 0, 1, 0};
   int size = sizeof(arr)/sizeof(arr[0]);
   //sort an array
   sort(arr, arr + size);
   //call function
   int total = Rearrange_min_sum(arr, size);
   cout<<"Rearrangement of an array to minimize sum i.e. "<<total<<" of product of consecutive pair elements is: ";
   for(int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   return 0;
}

Output

If we run the above code it will generate the following output

Rearrangement of an array to minimize sum i.e. 7 of product of consecutive pair elements is: 7 0 5 0 5 1 2 1

The above is the detailed content of Rearrange an array so that the sum of the products of consecutive pairs of elements is minimal, written in C++. For more information, please follow other related articles on the PHP Chinese website!