Given an array arr[] containing a permutation of first N natural numbers. In one operation, remove a pair (X, Y) from the array and insert (X + Y + 1) / 2 into the array. The task is to find the smallest array element that can be left remaining in the array by performing the given operation exactly N – 1 times and the N – 1 pairs. If multiple solutions exist, then print any one of them.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: {2}, { (2, 4), (3, 3), (1, 3) }
Explanation:
Selecting a pair(arr[1], arr[3]) modifies the array arr[] = {1, 3, 3}
Selecting a pair(arr[1], arr[2]) modifies the array arr[] = {1, 3}
Selecting a pair(arr[0], arr[1]) modifies the array arr[] = {2}
Therefore, the smallest element left in array = {2} and the pairs that can be selected are {(2, 4), (3, 3), (1, 3)}.Input: arr[] = {3, 2, 1}
Output: {2}, { (3, 2), (3, 1) }
Approach:The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Initialize an array, say pairsArr[] to store all the pairs that can be selected by performing the given operations.
- Create a priority queue, say pq to store all the array elements in the priority queue.
- Traverse pq while count elements left in pq is greater than 1 and in each operation pop the top two elements(X, Y) of pq, store (X, Y) in pairsArr[] and insert an element having the value (X + Y + 1) / 2 in pq.
- Finally, print the value of the element left in pq and pairsArr[].
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to print the smallest element left// in the array and the pairs by given operationvoid smallestNumberLeftInPQ(int arr[], int N){ // Stores array elements and return // the minimum element of arr[] in O(1) priority_queue<int> pq; // Stores all the pairs that can be // selected by the given operations vector<pair<int, int> > pairsArr; // Traverse the array arr[] for (int i = 0; i < N; i++) { pq.push(arr[i]); } // Traverse pq while count of elements // left in pq greater than 1 while (pq.size() > 1) { // Stores top element of pq int X = pq.top(); // Pop top element of pq pq.pop(); // Stores top element of pq int Y = pq.top(); // Pop top element of pq pq.pop(); // Insert (X + Y + 1) / 2 in pq pq.push((X + Y + 1) / 2); // Insert the pair (X, Y) // in pairsArr[] pairsArr.push_back({ X, Y }); } // Print the element left in pq // by performing the given operations cout << "{" << pq.top() << "}, "; // Stores count of elements // in pairsArr[] int sz = pairsArr.size(); // Print all the pairs that can // be selected in given operations for (int i = 0; i < sz; i++) { // If i is the first // index of pairsArr[] if (i == 0) { cout << "{ "; } // Print current pairs of pairsArr[] cout << "(" << pairsArr[i].first << ", " << pairsArr[i].second << ")"; // If i is not the last index // of pairsArr[] if (i != sz - 1) { cout << ", "; } // If i is the last index // of pairsArr[] if (i == sz - 1) { cout << " }"; } }}// Driver Codeint main(){ int arr[] = { 3, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); smallestNumberLeftInPQ(arr, N);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to print the smallest element left// in the array and the pairs by given operationstatic void smallestNumberLeftInPQ(int arr[], int N){ // Stores array elements and return // the minimum element of arr[] in O(1) PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> Integer.compare(y, x)); // Stores all the pairs that can be // selected by the given operations Vector<pair > pairsArr = new Vector<>(); // Traverse the array arr[] for (int i = 0; i < N; i++) { pq.add(arr[i]); } // Traverse pq while count of elements // left in pq greater than 1 while (pq.size() > 1) { // Stores top element of pq int X = pq.peek(); // Pop top element of pq pq.remove(); // Stores top element of pq int Y = pq.peek(); // Pop top element of pq pq.remove(); // Insert (X + Y + 1) / 2 in pq pq.add((X + Y + 1) / 2); // Insert the pair (X, Y) // in pairsArr[] pairsArr.add(new pair( X, Y )); } // Print the element left in pq // by performing the given operations System.out.print("{" + pq.peek()+ "}, "); // Stores count of elements // in pairsArr[] int sz = pairsArr.size(); // Print all the pairs that can // be selected in given operations for (int i = 0; i < sz; i++) { // If i is the first // index of pairsArr[] if (i == 0) { System.out.print("{ "); } // Print current pairs of pairsArr[] System.out.print("(" + pairsArr.get(i).first + ", " + pairsArr.get(i).second+ ")"); // If i is not the last index // of pairsArr[] if (i != sz - 1) { System.out.print(", "); } // If i is the last index // of pairsArr[] if (i == sz - 1) { System.out.print(" }"); } }}// Driver Codepublic static void main(String[] args){ int arr[] = { 3, 2, 1 }; int N = arr.length; smallestNumberLeftInPQ(arr, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approach# Function to print smallest # element left in the array # and the pairs by given operationdef smallestNumberLeftInPQ(arr, N): # Stores array elements and # return the minimum element # of arr[] in O(1) pq = [] # Stores all the pairs that can # be selected by the given operations pairsArr = [] # Traverse the array arr[] for i in range(N): pq.append(arr[i]) pq = sorted(pq) # Traverse pq while count of # elements left in pq greater # than 1 while (len(pq) > 1): # Stores top element of pq X = pq[-1] del pq[-1] # Stores top element of pq Y = pq[-1] # Pop top element of pq del pq[-1] # Insert (X + Y + 1) / 2 # in pq pq.append((X + Y + 1) // 2) # Insert the pair (X, Y) # in pairsArr[] pairsArr.append([X, Y]) pq = sorted(pq) # Print element left in pq # by performing the given # operations print("{", pq[-1], "}, ", end = "") # Stores count of elements # in pairsArr[] sz = len(pairsArr) # Print the pairs that can # be selected in given operations for i in range(sz): # If i is the first # index of pairsArr[] if (i == 0): print("{ ", end = "") # Print pairs of pairsArr[] print("(", pairsArr[i][0], ",", pairsArr[i][1], ")", end = "") # If i is not the last index # of pairsArr[] if (i != sz - 1): print(end = ", ") # If i is the last index # of pairsArr[] if (i == sz - 1): print(end = " }")# Driver Codeif __name__ == '__main__': arr = [3, 2, 1] N = len(arr) smallestNumberLeftInPQ(arr, N)# This code is contributed by Mohit Kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ public class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; }}// Function to print the smallest element left// in the array and the pairs by given operationstatic void smallestNumberLeftInPQ(int[] arr, int N){ // Stores array elements and return // the minimum element of []arr in O(1) List<int> pq = new List<int>(); // Stores all the pairs that can be // selected by the given operations List<pair> pairsArr = new List<pair>(); // Traverse the array []arr for(int i = 0; i < N; i++) { pq.Add(arr[i]); } pq.Sort(); pq.Reverse(); // Traverse pq while count of elements // left in pq greater than 1 while (pq.Count > 1) { // Stores top element of pq int X = pq[0]; // Pop top element of pq pq.RemoveAt(0); // Stores top element of pq int Y = pq[0]; // Pop top element of pq pq.RemoveAt(0); // Insert (X + Y + 1) / 2 in pq pq.Add((X + Y + 1) / 2); pq.Sort(); pq.Reverse(); // Insert the pair (X, Y) // in pairsArr[] pairsArr.Add(new pair(X, Y)); } // Print the element left in pq // by performing the given operations Console.Write("{" + pq[0] + "}, "); // Stores count of elements // in pairsArr[] int sz = pairsArr.Count; // Print all the pairs that can // be selected in given operations for(int i = 0; i < sz; i++) { // If i is the first // index of pairsArr[] if (i == 0) { Console.Write("{ "); } // Print current pairs of pairsArr[] Console.Write("(" + pairsArr[i].first + ", " + pairsArr[i].second + ")"); // If i is not the last index // of pairsArr[] if (i != sz - 1) { Console.Write(", "); } // If i is the last index // of pairsArr[] if (i == sz - 1) { Console.Write(" }"); } }}// Driver Codepublic static void Main(String[] args){ int[] arr = { 3, 2, 1 }; int N = arr.Length; smallestNumberLeftInPQ(arr, N);}}// This code is contributed by aashish1995 |
Javascript
<script>// JavaScript program to implement// the above approachclass pair{ constructor(first,second) { this.first = first; this.second = second; } }// Function to print the smallest element left// in the array and the pairs by given operationfunction smallestNumberLeftInPQ(arr,N){ // Stores array elements and return // the minimum element of arr[] in O(1) let pq = []; // Stores all the pairs that can be // selected by the given operations let pairsArr = []; // Traverse the array arr[] for (let i = 0; i < N; i++) { pq.push(arr[i]); } pq.sort(function(a,b){return b-a;}); // Traverse pq while count of elements // left in pq greater than 1 while (pq.length > 1) { // Stores top element of pq let X = pq[0]; // Pop top element of pq pq.shift(); // Stores top element of pq let Y = pq[0]; // Pop top element of pq pq.shift(); // Insert (X + Y + 1) / 2 in pq pq.push(Math.floor((X + Y + 1) / 2)); pq.sort(function(a,b){return b-a;}); // Insert the pair (X, Y) // in pairsArr[] pairsArr.push(new pair( X, Y )); } // Print the element left in pq // by performing the given operations document.write("{" + pq[0]+ "}, "); // Stores count of elements // in pairsArr[] let sz = pairsArr.length; // Print all the pairs that can // be selected in given operations for (let i = 0; i < sz; i++) { // If i is the first // index of pairsArr[] if (i == 0) { document.write("{ "); } // Print current pairs of pairsArr[] document.write("(" + pairsArr[i].first + ", " + pairsArr[i].second+ ")"); // If i is not the last index // of pairsArr[] if (i != sz - 1) { document.write(", "); } // If i is the last index // of pairsArr[] if (i == sz - 1) { document.write(" }"); } }}// Driver Codelet arr=[3, 2, 1 ];let N = arr.length;smallestNumberLeftInPQ(arr, N);// This code is contributed by patel2127</script> |
Output:
{2}, { (3, 2), (3, 1) }
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!