Minimize remaining array element by repeatedly replacing pairs by half of one more than their sum | Function to print 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 element left in pq by performing the given operations ; Stores count of elements in pairsArr [ ] ; Print the pairs that can be selected in given operations ; If i is the first index of pairsArr [ ] ; Print pairs of pairsArr [ ] ; If i is not the last index of pairsArr [ ] ; If i is the last index of pairsArr [ ] ; Driver Code
def smallestNumberLeftInPQ ( arr , N ) : NEW_LINE INDENT pq = [ ] NEW_LINE pairsArr = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT pq . append ( arr [ i ] ) NEW_LINE DEDENT pq = sorted ( pq ) NEW_LINE while ( len ( pq ) > 1 ) : NEW_LINE INDENT X = pq [ - 1 ] NEW_LINE del pq [ - 1 ] NEW_LINE Y = pq [ - 1 ] NEW_LINE del pq [ - 1 ] NEW_LINE pq . append ( ( X + Y + 1 ) // 2 ) NEW_LINE pairsArr . append ( [ X , Y ] ) NEW_LINE pq = sorted ( pq ) NEW_LINE DEDENT print ( " { " , pq [ - 1 ] , " } , ▁ " , end = " " ) NEW_LINE sz = len ( pairsArr ) NEW_LINE for i in range ( sz ) : NEW_LINE INDENT if ( i == 0 ) : NEW_LINE INDENT print ( " { ▁ " , end = " " ) NEW_LINE DEDENT print ( " ( " , pairsArr [ i ] [ 0 ] , " , " , pairsArr [ i ] [ 1 ] , " ) " , end = " " ) NEW_LINE if ( i != sz - 1 ) : NEW_LINE INDENT print ( end = " , ▁ " ) NEW_LINE DEDENT if ( i == sz - 1 ) : NEW_LINE INDENT print ( end = " ▁ } " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 2 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE smallestNumberLeftInPQ ( arr , N ) NEW_LINE DEDENT