Minimum cost for acquiring all coins with k extra coins allowed with every coin | Python3 program to acquire all n coins at minimum cost with multiple values of k . ; Converts coin [ ] to prefix sum array ; sort the coins values ; 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
import math as mt NEW_LINE def preprocess ( coin , n ) : NEW_LINE INDENT coin . sort ( ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT coin [ i ] += coin [ i - 1 ] NEW_LINE DEDENT DEDENT def minCost ( coin , n , k ) : NEW_LINE INDENT coins_needed = mt . ceil ( 1.0 * n / ( k + 1 ) ) NEW_LINE return coin [ coins_needed - 1 ] NEW_LINE DEDENT coin = [ 8 , 5 , 3 , 10 , 2 , 1 , 15 , 25 ] NEW_LINE n = len ( coin ) NEW_LINE preprocess ( coin , n ) NEW_LINE k = 3 NEW_LINE print ( minCost ( coin , n , k ) ) NEW_LINE k = 7 NEW_LINE print ( minCost ( coin , n , k ) ) NEW_LINE