Minimize Sum of an Array by at most K reductions | Java Program to implement the above approach ; Function to obtain the minimum possible sum from the array by K reductions ; Implements the MaxHeap ; Insert elements into the MaxHeap ; Remove the maximum ; Insert maximum / 2 ; Stores the sum of remaining elements ; Driver Code
import java . io . * ; import java . util . * ; class GFG { public static int minSum ( int a [ ] , int n , int k ) { PriorityQueue < Integer > maxheap = new PriorityQueue < > ( ( one , two ) -> two - one ) ; for ( int i = 0 ; i < n ; i ++ ) maxheap . add ( a [ i ] ) ; while ( maxheap . size ( ) > 0 && k > 0 ) { int max_ele = maxheap . poll ( ) ; maxheap . add ( max_ele / 2 ) ; k -= 1 ; } int sum = 0 ; while ( maxheap . size ( ) > 0 ) sum += maxheap . poll ( ) ; return sum ; } public static void main ( String [ ] args ) { int n = 4 ; int k = 3 ; int a [ ] = { 20 , 7 , 5 , 4 } ; System . out . println ( minSum ( a , n , k ) ) ; } }