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
function preprocess ( coin , n ) { coin . sort ( function ( a , b ) { return a - b ; } ) ; for ( let i = 1 ; i <= n - 1 ; i ++ ) coin [ i ] += coin [ i - 1 ] ; } function minCost ( coin , n , k ) { let coins_needed = Math . ceil ( 1.0 * n / ( k + 1 ) ) ; return coin [ coins_needed - 1 ] ; } let coin = [ 8 , 5 , 3 , 10 , 2 , 1 , 15 , 25 ] ; let n = coin . length ; preprocess ( coin , n ) ; let k = 3 ; document . write ( minCost ( coin , n , k ) + " " ) ; k = 7 ; document . write ( minCost ( coin , n , k ) ) ;