Reducir la array a un solo entero con la operación dada

Dada una array arr[] de N enteros de 1 a N. La tarea es realizar las siguientes operaciones N – 1 veces.  

1. Seleccione dos elementos X e Y de la array.
2. Eliminar los elementos elegidos de la array.
3. Agregue X ² + Y ² en la array.

Después de realizar las operaciones anteriores N – 1 veces, solo quedará un entero en la array. La tarea es imprimir el valor máximo posible de ese entero.

Ejemplos:  

Entrada: N = 3 
Salida: 170 
Explicación: Array inicial: arr[] = {1, 2, 3} 
Elija 2 y 3 y la array se convierte en arr[] = {1, 13} 
Realizando la operación nuevamente eligiendo los dos únicos quedan elementos, 
la array se convierte en arr[] = {170}, que es el valor máximo posible.

Entrada: N = 4 
Salida: 395642 

Enfoque: Para maximizar el valor del entero final tenemos que maximizar el valor de (X ² + Y ² ) . Entonces, cada vez que tenemos que elegir los dos valores máximos de la array. Almacene todos los enteros en una cola de prioridad. Cada vez, saque los 2 elementos principales y empuje el resultado de (X ² + Y ² ) en la cola de prioridad. El último elemento restante será el valor máximo posible del entero requerido.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the maximum
// integer after performing the operations
int reduceOne(int N)
{
    priority_queue<ll> pq;
 
    // Initialize priority queue with
    // 1 to N
    for (int i = 1; i <= N; i++)
        pq.push(i);
 
    // Perform the operations while
    // there are at least 2 elements
    while (pq.size() > 1) {
 
        // Get the maximum and
        // the second maximum
        ll x = pq.top();
        pq.pop();
        ll y = pq.top();
        pq.pop();
 
        // Push (x^2 + y^2)
        pq.push(x * x + y * y);
    }
 
    // Return the only element left
    return pq.top();
}
 
// Driver code
int main()
{
    int N = 3;
 
    cout << reduceOne(N);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
    // Function to return the maximum
    // integer after performing the operations
    static long reduceOne(int N)
    {
        // To create Max-Heap
        PriorityQueue<Long> pq = new
        PriorityQueue<Long>(Collections.reverseOrder());
 
        // Initialize priority queue with
        // 1 to N
        for (long i = 1; i <= N; i++)
            pq.add(i);
 
        // Perform the operations while
        // there are at least 2 elements
        while (pq.size() > 1)
        {
 
            // Get the maximum and
            // the second maximum
            long x = pq.poll();
            long y = pq.poll();
 
            // Push (x^2 + y^2)
            pq.add(x * x + y * y);
        }
 
        // Return the only element left
        return pq.peek();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 3;
        System.out.println(reduceOne(N));
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 implementation of the approach
 
from heapq import heappop, heappush, heapify
 
# Function to return the maximum
# integer after performing the operations
def reduceOne(N) :
    pq = []
     
    # Initialize priority queue with
    # 1 to N
    for i in range(1, N + 1):
        pq.append(i)
       
    # Used to implement max heap
    for i in range(0, N):
        pq[i] = -1*pq[i];
    heapify(pq)
     
    # Perform the operations while
    # there are at least 2 elements
    while(len(pq) > 1) :
     
        # Get the maximum and
        # the second maximum
        x = heappop(pq)
        y = heappop(pq)
     
        # Push (x^2 + y^2)
        heappush(pq, -1 * (x * x + y * y))
     
    # Return the only element left
    return -1*heappop(pq)
     
# Driver code
if __name__ == '__main__':
    N = 3
    print(reduceOne(N))
 
# This code is contributed by divyeshrabadiya07.

170

Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)