Minimize Sum of an Array by at most K reductions | Function to obtain the minimum possible sum from the array by K reductions ;  ; Insert elements into the MaxHeap ; Remove the maximum ; Insert maximum / 2 ; Stores the sum of remaining elements ; Driver code
def minSum ( a , n , k ) : NEW_LINE ' TABSYMBOL TABSYMBOL Implements ▁ the ▁ MaxHeap ' ' ' NEW_LINE INDENT q = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT q . append ( a [ i ] ) NEW_LINE DEDENT q = sorted ( q ) NEW_LINE while ( len ( q ) > 0 and k > 0 ) : NEW_LINE INDENT top = q [ - 1 ] // 2 NEW_LINE del q [ - 1 ] NEW_LINE q . append ( top ) NEW_LINE k -= 1 NEW_LINE q = sorted ( q ) NEW_LINE DEDENT sum = 0 NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT sum += q [ - 1 ] NEW_LINE del q [ - 1 ] NEW_LINE DEDENT return sum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 NEW_LINE k = 3 NEW_LINE a = [ 20 , 7 , 5 , 4 ] NEW_LINE print ( minSum ( a , n , k ) ) NEW_LINE DEDENT