Given an array arr[] of N integers from 1 to N. The task is to perform the following operations N – 1 times.
- Select two elements X and Y from the array.
- Delete the chosen elements from the array.
- Add X2 + Y2in the array.
After performing above operations N – 1 times only one integer will be left in the array. The task is to print the maximum possible value of that integer.
Examples:
Input: N = 3
Output: 170
Explanation: Initial array: arr[] = {1, 2, 3}
Choose 2 and 3 and the array becomes arr[] = {1, 13}
Performing the operation again by choosing the only two elements left,
the array becomes arr[] = {170} which is the maximum possible value.Input: N = 4
Output: 395642
Approach: To maximize the value of final integer we have to maximize the value of (X2 + Y2). So each time we have to choose the maximum two values from the array. Store all integers in a priority queue. Each time pop top 2 elements and push the result of (X2 + Y2) in the priority queue. The last remaining element will be the maximum possible value of the required integer.
Algorithm:
Step 1: Start
Step 2: Create a static function names reduceOne of long return type which take an integer N as input.
Step 3: Create a priority_queue of type long long int
Step 4: Now with the help of for loop initialize the priority queue from 1 to n.
Step 5: Loop while the size of priority_queue is greater than 1
Get the maximum element x from priority_queue and remove it
Get the second top element y from priority_queue and remove it
Step 6: Now calculate the value of x^2 + y^2 and add it to the priority queue
Step 7: Return the element left in the priority queue
Step 8: End
Below is the implementation of the above approach:
C++
// 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 operationsint 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 codeint main(){ int N = 3; cout << reduceOne(N); return 0;} |
Java
// Java implementation of the approachimport 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
# 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 codeif __name__ == '__main__': N = 3 print(reduceOne(N))# This code is contributed by divyeshrabadiya07. |
Javascript
function reduceOne(N) { // To create Max-Heap let pq = []; // Initialize priority queue with // 1 to N for (let i = 1; i <= N; i++){ pq.push(i); } pq.sort(); // Perform the operations while // there are at least 2 elements while (pq.length > 1) { // Get the maximum and // the second maximum let x = pq.pop(); let y = pq.pop(); // Push (x^2 + y^2) pq.push((x * x) +(y * y)); } // Return the only element left return pq.pop(); } let N = 3; console.log(reduceOne(N));// This code is contributed by utkarshshirode02 |
C#
using System;using System.Collections.Generic;class Program{ static int reduceOne(int N) { // To create Max-Heap var pq = new List<int>(); // Initialize priority queue with // 1 to N for (int i = 1; i <= N; i++) { pq.Add(i); } pq.Sort(); // Perform the operations while // there are at least 2 elements while (pq.Count > 1) { // Get the maximum and // the second maximum int x = pq[pq.Count - 1]; pq.RemoveAt(pq.Count - 1); int y = pq[pq.Count - 1]; pq.RemoveAt(pq.Count - 1); // Push (x^2 + y^2) pq.Add(x * x + y * y); pq.Sort(); } // Return the only element left return pq[0]; } static void Main(string[] args) { int N = 3; Console.WriteLine(reduceOne(N)); }} |
170
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
