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
< ? php function computeCost ( $ arr , $ N , $ X ) { $ cost = 0 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) $ cost += abs ( $ arr [ $ i ] - $ X ) ; return $ cost ; } function minCostToMakeElementEqual ( $ arr , $ N ) { $ low ; $ high ; $ low = $ high = $ arr [ 0 ] ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { if ( $ low > $ arr [ $ i ] ) $ low = $ arr [ $ i ] ; if ( $ high < $ arr [ $ i ] ) $ high = $ arr [ $ i ] ; } while ( ( $ high - $ low ) > 2 ) { $ mid1 = $ low + ( floor ( $ high - $ low ) / 3 ) ; $ mid2 = $ high - ( $ high - $ low ) / 3 ; $ cost1 = computeCost ( $ arr , $ N , $ mid1 ) ; $ cost2 = computeCost ( $ arr , $ N , $ mid2 ) ; if ( $ cost1 < $ cost2 ) $ high = $ mid2 ; else $ low = $ mid1 ; } return computeCost ( $ arr , $ N , ( $ low + $ high ) / 2 ) ; } $ arr = array ( 1 , 100 , 101 ) ; $ N = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; echo minCostToMakeElementEqual ( $ arr , $ N ) ; ? >