Minimize remaining array element by repeatedly replacing pairs by half of one more than their sum | Java program to implement the above approach ; 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void smallestNumberLeftInPQ ( int arr [ ] , int N ) { PriorityQueue < Integer > pq = new PriorityQueue < > ( ( x , y ) -> Integer . compare ( y , x ) ) ; Vector < pair > pairsArr = new Vector < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { pq . add ( arr [ i ] ) ; } while ( pq . size ( ) > 1 ) { int X = pq . peek ( ) ; pq . remove ( ) ; int Y = pq . peek ( ) ; pq . remove ( ) ; pq . add ( ( X + Y + 1 ) / 2 ) ; pairsArr . add ( new pair ( X , Y ) ) ; } System . out . print ( " { " + pq . peek ( ) + " } , ▁ " ) ; int sz = pairsArr . size ( ) ; for ( int i = 0 ; i < sz ; i ++ ) { if ( i == 0 ) { System . out . print ( " { ▁ " ) ; } System . out . print ( " ( " + pairsArr . get ( i ) . first + " , ▁ " + pairsArr . get ( i ) . second + " ) " ) ; if ( i != sz - 1 ) { System . out . print ( " , ▁ " ) ; } if ( i == sz - 1 ) { System . out . print ( " ▁ } " ) ; } } } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 2 , 1 } ; int N = arr . length ; smallestNumberLeftInPQ ( arr , N ) ; } }