Minimum cost for acquiring all coins with k extra coins allowed with every coin | C # program to acquire all n coins at minimum cost with multiple values of k . ; 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
import java . io . * ; import java . util . Arrays ; public class GFG { static void preprocess ( int [ ] coin , int n ) { Arrays . sort ( coin ) ; for ( int i = 1 ; i <= n - 1 ; i ++ ) coin [ i ] += coin [ i - 1 ] ; } static int minCost ( int [ ] coin , int n , int k ) { int coins_needed = ( int ) Math . ceil ( 1.0 * n / ( k + 1 ) ) ; return coin [ coins_needed - 1 ] ; } static public void main ( String [ ] args ) { int [ ] coin = { 8 , 5 , 3 , 10 , 2 , 1 , 15 , 25 } ; int n = coin . length ; preprocess ( coin , n ) ; int k = 3 ; System . out . println ( minCost ( coin , n , k ) ) ; k = 7 ; System . out . println ( minCost ( coin , n , k ) ) ; } }