# What is the minimum number of coins to make the change?

Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, … , Cm} valued coins, what is the minimum number of coins to make the change? If it’s not possible to make change, print -1.

Examples:

Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents

Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents

Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, … , Cm} valued coins, what is the minimum number of coins to make the change? If it’s not possible to make change, print -1.

Examples:

Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents

Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents

Below is Dynamic Programming based solution.

`// A Dynamic Programming based C++ program to find minimum of coins`

`// to make a given change V`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`// m is size of coins array (number of different coins)`

`int` `minCoins(` `int` `coins[], ` `int` `m, ` `int` `V)`

`{`

`` `// table[i] will be storing the minimum number of coins`

`` `// required for i value. So table[V] will have result`

`` `int` `table[V+1];`

`` `// Base case (If given value V is 0)`

`` `table = 0;`

`` `// Initialize all table values as Infinite`

`` `for` `(` `int` `i=1; i<=V; i++)`

`` `table[i] = INT_MAX;`

`` `// Compute minimum coins required for all`

`` `// values from 1 to V`

`` `for` `(` `int` `i=1; i<=V; i++)`

`` `{`

`` `// Go through all coins smaller than i`

`` `for` `(` `int` `j=0; j<m; j++)`

`` `if` `(coins[j] <= i)`

`` `{`

`` `int` `sub_res = table[i-coins[j]];`

`` `if` `(sub_res != INT_MAX && sub_res + 1 < table[i])`

`` `table[i] = sub_res + 1;`

`` `}`

`` `}`

``

`` `if` `(table[V]==INT_MAX)`

`` `return` `-1;`

``

`` `return` `table[V];`

`}`

`// Driver program to test above function`

`int` `main()`

`{`

`` `int` `coins[] = {9, 6, 5, 1};`

`` `int` `m = ` `sizeof` `(coins)/` `sizeof` `(coins);`

`` `int` `V = 11;`

`` `cout << ` `"Minimum coins required is "`

`` `<< minCoins(coins, m, V);`

`` `return` `0;`

`}`

Output:

Minimum coins required is 2

Time complexity of the above solution is O(mV).