Minimize remaining array element by removing pairs and replacing them with their average | C ++ program to implement the above approach ; Function to find the smallest element left in the array by removing pairs and inserting their average ; Stores array elements such that the largest element present at top of PQ ; Traverse the array ; Insert arr [ i ] into PQ ; Iterate over elements of PQ while count of elements in PQ greater than 1 ; Stores largest element of PQ ; Pop the largest element of PQ ; Stores largest element of PQ ; Pop the largest element of PQ ; Insert the ceil value of average of top1 and top2 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSmallestNumLeft ( int arr [ ] , int N ) { priority_queue < int > PQ ; for ( int i = 0 ; i < N ; i ++ ) { PQ . push ( arr [ i ] ) ; } while ( PQ . size ( ) > 1 ) { int top1 = PQ . top ( ) ; PQ . pop ( ) ; int top2 = PQ . top ( ) ; PQ . pop ( ) ; PQ . push ( ( top1 + top2 + 1 ) / 2 ) ; } return PQ . top ( ) ; } int main ( ) { int arr [ ] = { 30 , 16 , 40 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << findSmallestNumLeft ( arr , N ) ; return 0 ; }