Minimize remaining array element by repeatedly replacing pairs by half of one more than their sum | Utility pair ; Function to print the smallest element left in the array and the pairs by given operation ; Stores array elements and return the minimum element of arr [ ] in O ( 1 ) ; Stores all the pairs that can be selected by the given operations ; Traverse the array arr [ ] ; Traverse pq while count of elements left in pq greater than 1 ; Stores top element of pq ; Pop top element of pq ; Stores top element of pq ; Pop top element of pq ; Insert ( X + Y + 1 ) / 2 in pq ; Insert the pair ( X , Y ) in pairsArr [ ] ; Print the element left in pq by performing the given operations ; Stores count of elements in pairsArr [ ] ; Print all the pairs that can be selected in given operations ; If i is the first index of pairsArr [ ] ; Print current pairs of pairsArr [ ] ; If i is not the last index of pairsArr [ ] ; If i is the last index of pairsArr [ ] ; Driver Code
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } function smallestNumberLeftInPQ ( arr , N ) { let pq = [ ] ; let pairsArr = [ ] ; for ( let i = 0 ; i < N ; i ++ ) { pq . push ( arr [ i ] ) ; } pq . sort ( function ( a , b ) { return b - a ; } ) ; while ( pq . length > 1 ) { let X = pq [ 0 ] ; pq . shift ( ) ; let Y = pq [ 0 ] ; pq . shift ( ) ; pq . push ( Math . floor ( ( X + Y + 1 ) / 2 ) ) ; pq . sort ( function ( a , b ) { return b - a ; } ) ; pairsArr . push ( new pair ( X , Y ) ) ; } document . write ( " " + pq [ 0 ] + " " ) ; let sz = pairsArr . length ; for ( let i = 0 ; i < sz ; i ++ ) { if ( i == 0 ) { document . write ( " " ) ; } document . write ( " " + pairsArr [ i ] . first + " " + pairsArr [ i ] . second + " " ) ; if ( i != sz - 1 ) { document . write ( " " ) ; } if ( i == sz - 1 ) { document . write ( " " ) ; } } } let arr = [ 3 , 2 , 1 ] ; let N = arr . length ; smallestNumberLeftInPQ ( arr , N ) ;