Given an array arr[] of size N, the task is to find the smallest possible remaining array element by repeatedly removing a pair, say (arr[i], arr[j]) from the array and inserting the Ceil value of their average.
Examples:
Input: arr[] = { 1, 2, 3 }
Output: 2
Explanation:
Removing the pair (arr[1], arr[2]) from arr[] and inserting (arr[1] + arr[2] + 1) / 2 into arr[] modifies arr[] to { 1, 2 }.
Removing the pair (arr[0], arr[1]) from arr[] and inserting (arr[0] + arr[1] + 1) / 2 into arr[] modifies arr[] to { 2 }.
Therefore, the required output is 2.Input: arr[] = { 30, 16, 40 }
Output: 26
Explanation:
Removing the pair (arr[0], arr[2]) from arr[] and inserting (arr[0] + arr[2] + 1) / 2 into arr[] modifies arr[] to { 16, 35 } .
Removing the pair (arr[0], arr[1]) from arr[] and inserting (arr[0] + arr[1] + 1) / 2 into arr[] modifies arr[] to { 26 } .
Therefore, the required output is 26.
Approach: The problem can be solved using Greedy technique. The idea is to repeatedly remove the maximum and the second-maximum array element and insert their average. Finally, print the smallest element left in the array.
- Initialize a priority_queue, say PQ, to store the array elements such that the largest element is always present at the top of PQ.
- Traverse the array and store all the array elements in PQ.
- Iterate over the elements of the priority_queue while count of elements in the priority_queue is greater than 1. In every iteration, pop the top two elements from PQ and insert the Ceil value of their average.
- Finally, print the element left in PQ.
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 find the smallest element// left in the array by removing pairs// and inserting their averageint findSmallestNumLeft(int arr[], int N){ // Stores array elements such that the // largest element present at top of PQ priority_queue<int> PQ; // Traverse the array for (int i = 0; i < N; i++) { // Insert arr[i] into PQ PQ.push(arr[i]); } // Iterate over elements of PQ while count // of elements in PQ greater than 1 while (PQ.size() > 1) { // Stores largest element of PQ int top1 = PQ.top(); // Pop the largest element of PQ PQ.pop(); // Stores largest element of PQ int top2 = PQ.top(); // Pop the largest element of PQ PQ.pop(); // Insert the ceil value of average // of top1 and top2 PQ.push((top1 + top2 + 1) / 2); } return PQ.top();}// Driver Codeint main(){ int arr[] = { 30, 16, 40 }; int N = sizeof(arr) / sizeof(arr[0]); cout << findSmallestNumLeft( arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.PriorityQueue;class GFG{// Function to find the smallest element// left in the array by removing pairs// and inserting their averagestatic int findSmallestNumLeft(int arr[], int N){ // Stores array elements such that the // largest element present at top of PQ PriorityQueue<Integer> PQ = new PriorityQueue<Integer>((a,b)->b-a); // Traverse the array for (int i = 0; i < N; i++) { // Insert arr[i] into PQ PQ.add(arr[i]); } // Iterate over elements of PQ while count // of elements in PQ greater than 1 while (PQ.size() > 1) { // Stores largest element of PQ int top1 = PQ.peek(); // Pop the largest element of PQ PQ.remove(); // Stores largest element of PQ int top2 = PQ.peek(); // Pop the largest element of PQ PQ.remove(); // Insert the ceil value of average // of top1 and top2 PQ.add((top1 + top2 + 1) / 2); } return PQ.peek();}// Driver Codepublic static void main(String[] args){ int arr[] = { 30, 16, 40 }; int N = arr.length; System.out.print(findSmallestNumLeft( arr, N));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approach# Function to find the smallest element# left in the array by removing pairs# and inserting their averagedef findSmallestNumLeft(arr, N): # Stores array elements such that the # largest element present at top of PQ PQ = [] # Traverse the array for i in range(N): # Insert arr[i] into PQ PQ.append(arr[i]) # Iterate over elements of PQ while count # of elements in PQ greater than 1 PQ = sorted(PQ) while (len(PQ) > 1): # Stores largest element of PQ top1 = PQ[-1] # Pop the largest element of PQ del PQ[-1] # Stores largest element of PQ top2 = PQ[-1] # Pop the largest element of PQ del PQ[-1] # Insert the ceil value of average # of top1 and top2 PQ.append((top1 + top2 + 1) // 2) PQ = sorted(PQ) return PQ[-1]# Driver Codeif __name__ == '__main__': arr = [ 30, 16, 40 ] N = len(arr) print (findSmallestNumLeft(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 { // Function to find the smallest element // left in the array by removing pairs // and inserting their average static int findSmallestNumLeft(int[] arr, int N) { // Stores array elements such that the // largest element present at top of PQ List<int> PQ = new List<int>(); // Traverse the array for (int i = 0; i < N; i++) { // Insert arr[i] into PQ PQ.Add(arr[i]); } PQ.Sort(); PQ.Reverse(); // Iterate over elements of PQ while count // of elements in PQ greater than 1 while (PQ.Count > 1) { // Stores largest element of PQ int top1 = PQ[0]; // Pop the largest element of PQ PQ.RemoveAt(0); // Stores largest element of PQ int top2 = PQ[0]; // Pop the largest element of PQ PQ.RemoveAt(0); // Insert the ceil value of average // of top1 and top2 PQ.Add((top1 + top2 + 1) / 2); PQ.Sort(); PQ.Reverse(); } return PQ[0]; } // Driver code public static void Main() { int[] arr = { 30, 16, 40 }; int N = arr.Length; Console.Write(findSmallestNumLeft(arr, N)); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the smallest element// left in the array by removing pairs// and inserting their averagefunction findSmallestNumLeft(arr, N){ // Stores array elements such that the // largest element present at top of PQ let PQ = []; // Traverse the array for (let i = 0; i < N; i++) { // Insert arr[i] into PQ PQ.push(arr[i]); } PQ.sort(function(a,b){return b-a;}); // Iterate over elements of PQ while count // of elements in PQ greater than 1 while (PQ.length > 1) { // Stores largest element of PQ let top1 = PQ[0]; // Pop the largest element of PQ PQ.shift(); // Stores largest element of PQ let top2 = PQ[0]; // Pop the largest element of PQ PQ.shift(); // Insert the ceil value of average // of top1 and top2 PQ.push(Math.floor((top1 + top2 + 1) / 2)); PQ.sort(function(a,b){return b-a;}); } return PQ[0];}// Driver Codelet arr = [ 30, 16, 40];let N = arr.length;document.write(findSmallestNumLeft( arr, N));// This code is contributed by unknown2108</script> |
Output:
26
Time Complexity: O(N*logN), as we are using a loop to traverse N times and priority queue operation will take logN time.
Auxiliary Space: O(N), as we are using extra space for priority queue.
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!
