Minimum cost for acquiring all coins with k extra coins allowed with every coin | Converts coin [ ] to prefix sum array ; sort the coins value ; Maintain prefix sum array ; Function to calculate min cost when we can get k extra coins after paying cost of one . ; calculate no . of coins needed ; return sum of from prefix array ; Driver Code
< ? php function preprocess ( & $ coin , $ n ) { sort ( $ coin ) ; for ( $ i = 1 ; $ i <= $ n - 1 ; $ i ++ ) $ coin [ $ i ] += $ coin [ $ i - 1 ] ; } function minCost ( & $ coin , $ n , $ k ) { $ coins_needed = ceil ( 1.0 * $ n / ( $ k + 1 ) ) ; return $ coin [ $ coins_needed - 1 ] ; } $ coin = array ( 8 , 5 , 3 , 10 , 2 , 1 , 15 , 25 ) ; $ n = sizeof ( $ coin ) ; preprocess ( $ coin , $ n ) ; $ k = 3 ; echo minCost ( $ coin , $ n , $ k ) . " STRNEWLINE " ; $ k = 7 ; echo minCost ( $ coin , $ n , $ k ) . " STRNEWLINE " ; ? >