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

PHPz
Release: 2023-08-26 10:57:06
forward
997 people have browsed it

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  using namespace std; int Rearrange_min_sum(int arr[], int size){ vector 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()); 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. "<
            
    Copy after login

    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
    Copy after login

    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!

    Related labels:
    source:tutorialspoint.com
    Statement of this Website
    The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn