Minimum Cost to make all array elements equal using given operations | Python3 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
def lowerBound ( array , length , value ) : NEW_LINE INDENT low = 0 NEW_LINE high = length NEW_LINE while ( low < high ) : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE if ( value <= array [ mid ] ) : NEW_LINE INDENT high = mid NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT return low NEW_LINE DEDENT def costCalculation ( current , arr , n , pref , a , r , minimum ) : NEW_LINE INDENT index = lowerBound ( arr , len ( arr ) , current ) NEW_LINE left = index * current - pref [ index ] NEW_LINE right = ( pref [ n ] - pref [ index ] - ( n - index ) * current ) NEW_LINE res = min ( left , right ) NEW_LINE left -= res NEW_LINE right -= res NEW_LINE total = res * minimum NEW_LINE total += left * a NEW_LINE total += right * r NEW_LINE return total NEW_LINE DEDENT def solve ( arr , n , a , r , m ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE minimum = min ( a + r , m ) NEW_LINE pref = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT pref [ i + 1 ] = pref [ i ] + arr [ i ] NEW_LINE DEDENT ans = 10000 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans = min ( ans , costCalculation ( arr [ i ] , arr , n , pref , a , r , minimum ) ) NEW_LINE DEDENT ans = min ( ans , costCalculation ( pref [ n ] // n , arr , n , pref , a , r , minimum ) ) NEW_LINE ans = min ( ans , costCalculation ( pref [ n ] // n + 1 , arr , n , pref , a , r , minimum ) ) NEW_LINE print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 5 , 3 , 6 , 5 ] NEW_LINE A = 1 NEW_LINE R = 2 NEW_LINE M = 4 NEW_LINE size = len ( arr ) NEW_LINE solve ( arr , size , A , R , M ) NEW_LINE DEDENT