Reduce an array to an integer using the given operation, implemented in C++

Given an integer variable Number as input. Let us consider an array containing elements in the range 1 to Number. The order of the elements can be arbitrary. If we perform Number-1 operations on the array, the operation is as follows:

• We select two elements A and B from the array

• from Remove A and B from the array

• Add the sum of the squares of A and B to the array

Eventually we will get a single integer value ;The goal is to find the maximum possible value for that element.

Using priority queue

• In order to maximize the final result, we need to choose A and B to make them as large as possible.

• In order to find the largest A and B, we will use a priority queue to store the element values ​​​​in it.

• Priority queue stores elements in descending order.

• The topmost element has the largest value, and so on. So after popping both elements, we'll push their squares into the queue again.

• Will pop and push Number-1 times to get the desired result.

Example

Input - Number=2

Output -A single element after the array is reduced :5

Explanation - Assume that the elements in the array are [1 2]

After inserting into the priority queue: 2 1

A=5, B =4 : A² B²=1 4=5

Last element: 5

Input -Number=5

Output - Single element after array reduction: 5

Explanation - Assume that the elements in the array are [5 1 2 4 3]

After inserting into the priority queue: 5 4 3 2 1

A=5, B=4 : A² B²=25 16=41 : 41 3 2 1

A=41, B=3 : A² B²=1681 9=1690 : 1690 2 1

A=1690, B=2 : A² B²=1681 4=2856104 : 2856104 1

A=2856104 , B=1 : A² B ²=1187163712 1=1187163713 : 1187163713

Last element: 1187163713

The method used in the following program is as follows

In this method, we will give priority The queue is set up to store the elements of the array in descending order. Pop the two largest elements and push the sum of their squares back into the queue until only one value remains.

• Get the input variable Number.

• Set the data type of the result to long long integer - lli

• The function reduceArray(int Num) accepts the input number and returns it using the above The largest single integer calculated by the operation.

• Use a priority queue pQueue.

• Use a while loop to fill numbers 1 to N into pQueue.

• When i

• Now pQueue stores integers 1 to N in descending order, with size N .

• Use a while loop to traverse pQueue until its size >= 1.

• Set the maximum value to var1=pQueue.top() and pop it.

• Set the next maximum value to var2=pQueue.top() and pop it.

• Set var1 to its square and set var2 to its square.

• Push var1 var2 into pQueue again.

• At the end of the while loop, return the top element.

• Print the result in the main function.

Example

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int reduceArray(int Num){
   priority_queue<lli> pQueue;
   int i=1;
   while(i<=Num){
      pQueue.push(i);
      i=i+1;
   }
   while (pQueue.size() > 1) {
      lli var1 = pQueue.top();
      pQueue.pop();
      lli var2 = pQueue.top();
      pQueue.pop();
      var1=var1*var1;
      var2=var2*var2;
      pQueue.push(var1+var2);
   }
   return pQueue.top();
}
int main(){
   int Number = 5;
   cout<<"Single element after array reduction: "<<reduceArray(Number);
   return 0;
}

Output

If we run the above code, the following output will be generated

Single element after array reduction: 1187163713

The above is the detailed content of Reduce an array to an integer using the given operation, implemented in C++. For more information, please follow other related articles on the PHP Chinese website!