Make all array elements equal with minimum cost | Utility method to compute cost , when all values of array are made equal to X ; Method to find minimum cost to make all elements equal ; Setting limits for ternary search by smallest and largest element ; loop until difference between low and high become less than 3 , because after that mid1 and mid2 will start repeating ; mid1 and mid2 are representative array equal values of search space ; if mid2 point gives more total cost , skip third part ; if mid1 point gives more total cost , skip first part ; computeCost gets optimum cost by sending average of low and high as X ; Driver code
def computeCost ( arr , N , X ) : NEW_LINE INDENT cost = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT cost += abs ( arr [ i ] - X ) NEW_LINE DEDENT return cost NEW_LINE DEDENT def minCostToMakeElementEqual ( arr , N ) : NEW_LINE INDENT low = high = arr [ 0 ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( low > arr [ i ] ) : low = arr [ i ] NEW_LINE if ( high < arr [ i ] ) : high = arr [ i ] NEW_LINE DEDENT while ( ( high - low ) > 2 ) : NEW_LINE INDENT mid1 = low + ( high - low ) // 3 NEW_LINE mid2 = high - ( high - low ) // 3 NEW_LINE cost1 = computeCost ( arr , N , mid1 ) NEW_LINE cost2 = computeCost ( arr , N , mid2 ) NEW_LINE if ( cost1 < cost2 ) : NEW_LINE INDENT high = mid2 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid1 NEW_LINE DEDENT DEDENT return computeCost ( arr , N , ( low + high ) // 2 ) NEW_LINE DEDENT arr = [ 1 , 100 , 101 ] NEW_LINE N = len ( arr ) NEW_LINE print ( minCostToMakeElementEqual ( arr , N ) ) NEW_LINE