Minimize array sum by replacing greater and smaller elements of pairs by half and double of their values respectively atmost K times | Java implementation of the above approach ; Function to find the minimum sum of array elements by given operations ; Base case ; Return 0 ; Base case ; Stores all the array elements in sorted order ; Traverse the array ; Insert current element into multiset ; Perform each operation ; Stores smallest element of ms ; Stores the largest element of ms ; Stores updated value of smallest element of ms by given operations ; Stores updated value of largest element of ms by given operations ; If the value of a + b less than the sum of smallest and largest array element ; Erase the smallest element ; Erase the largest element ; Insert the updated value of the smallest element ; Insert the updated value of the smallest element ; Stores sum of array elements ; Traverse the multiset ; Update ans ; Driver Code
import java . util . * ; class GFG { static int minimum_possible_sum ( int arr [ ] , int n , int k ) { if ( n == 0 ) { return 0 ; } if ( n == 1 ) { return arr [ 0 ] ; } Vector < Integer > ms = new Vector < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { ms . add ( arr [ i ] ) ; } Collections . sort ( ms ) ; for ( int i = 0 ; i < k ; i ++ ) { int smallest_element = ms . get ( 0 ) ; int largest_element = ms . get ( ms . size ( ) - 1 ) ; int a = smallest_element * 2 ; int b = largest_element / 2 ; if ( a + b < smallest_element + largest_element ) { ms . remove ( 0 ) ; ms . remove ( ms . size ( ) - 1 ) ; ms . add ( a ) ; ms . add ( b ) ; Collections . sort ( ms ) ; } } int ans = 0 ; for ( int x : ms ) { ans += x ; } return ans ; } public static void main ( String [ ] args ) { int arr [ ] = { 50 , 1 , 100 , 100 , 1 } ; int K = 2 ; int n = arr . length ; System . out . print ( minimum_possible_sum ( arr , n , K ) ) ; } }