Minimum Cost to make all array elements equal using given operations | Java implementation to find the minimum cost to make all array elements equal ; Checks if the value is less than middle element of the array ; Function that returns the cost of making all elements equal to current element ; Compute the lower bound of current element ; Calculate the requirement of add operation ; Calculate the requirement of subtract operation ; Compute minimum of left and right ; Computing the total cost of add and subtract operations ; Function that prints minimum cost of making all elements equal ; Sort the given array ; Calculate minimum from a + r and m ; Compute prefix sum and store in pref array ; Find the minimum cost from the given elements ; Finding the minimum cost from the other cases where minimum cost can occur ; Printing the minimum cost of making all elements equal ; Driver Code ; Function Call
import java . lang . * ; import java . util . * ; class GFG { public static int lowerBound ( int [ ] array , int length , int value ) { int low = 0 ; int high = length ; while ( low < high ) { final int mid = ( low + high ) / 2 ; if ( value <= array [ mid ] ) { high = mid ; } else { low = mid + 1 ; } } return low ; } public static int costCalculation ( int current , int arr [ ] , int n , int pref [ ] , int a , int r , int minimum ) { int index = lowerBound ( arr , arr . length , current ) ; int left = index * current - pref [ index ] ; int right = pref [ n ] - pref [ index ] - ( n - index ) * current ; int res = Math . min ( left , right ) ; left -= res ; right -= res ; int total = res * minimum ; total += left * a ; total += right * r ; return total ; } public static void solve ( int arr [ ] , int n , int a , int r , int m ) { Arrays . sort ( arr ) ; int minimum = Math . min ( a + r , m ) ; int [ ] pref = new int [ n + 1 ] ; Arrays . fill ( pref , 0 ) ; for ( int i = 0 ; i < n ; i ++ ) pref [ i + 1 ] = pref [ i ] + arr [ i ] ; int ans = 10000 ; for ( int i = 0 ; i < n ; i ++ ) ans = Math . min ( ans , costCalculation ( arr [ i ] , arr , n , pref , a , r , minimum ) ) ; ans = Math . min ( ans , costCalculation ( pref [ n ] / n , arr , n , pref , a , r , minimum ) ) ; ans = Math . min ( ans , costCalculation ( pref [ n ] / n + 1 , arr , n , pref , a , r , minimum ) ) ; System . out . println ( ans ) ; } public static void main ( String args [ ] ) { int arr [ ] = { 5 , 5 , 3 , 6 , 5 } ; int A = 1 , R = 2 , M = 4 ; int size = arr . length ; solve ( arr , size , A , R , M ) ; } }