# Minimum coins for a change

The minimum coins change programming problem is as below.
Given.
a) A coin of bigger value to be changed. Say a coin of value \$ 10 is to be changed.
b) A set of available coins. The assumption is that we have a set of infinite coins of values [ \$1, \$ 4, \$ 9, \$ 16 ].
The goal is to find the minimum number of smaller coins for exchanging a coin of bigger value i.e \$ 10 with coins of smaller values.

Example:
If a coin of value \$ 10 is to be changed with coins of values [ \$ 1, \$ 4, \$ 9, \$ 16 ] such that we get the minimum coins
a) \$ 10 = \$ 1 + \$ 9 i.e ( 2 coins )
b) \$ 10 = \$ 1 + \$ 1 + \$ 1 … + \$ 1 ( 10 times ) ( 10 coins )
c) \$ 10 = \$ 1 + \$ 1 + \$ 4 + \$ 4 ( 4 coins )
Thus minimum coins that we need is 2. Solving minimum coins for change problem

We begin by finding the minimum number of coins for each denomination from \$ 1 till the denomination of bigger coin i.e \$ 10. using the coins from the available set.

Thus,

• Base case : We need 0 coins for making a change for \$ 0. i.e DP [ 0 ] = 0
• For \$ 1 we need only 1 coin from the set. (i.e \$ 1). We store this value in a DP table. i.e DP [ 1 ] = 1. i.e for exchanging \$ 1 we need a minimum on 1 coin.
• For \$ 2 we being by using \$ 1 coin from the set i.e 1 coin but we still need to find the minimum number of coins needs for remaining \$ 1 i.e the deficit as \$ 2 - \$ 1 = \$ 1.
Now we can use DP table to fetch the minimum number of coins used to make change for \$ 1; i.e value of DP [ 1 ] which is 1.
So for \$ 2 we can make change using 2 coins.
i.e \$ 2 = 1 + (DP [ \$ 2 - \$ 1 ])
\$ 2 = 1 + DP [ 1 ] = 1 + 1 = 2
• For \$ 9 we need only 1 coin from the set i.e \$ 9 coin.
• From \$ 10 we can use 1 coin of value \$ 9 but for the remaining \$ 1 ( \$ 10 - \$ 9 ), we make use of DP [ 1 ].
i.e \$ 10 = 1 + DP [ \$ 10 - \$ 9 ]
i.e \$ 10 = 1 + DP [ \$ 1 ]
i.e \$ 10 = 1 + 1 = 2 coins.

Program for finding the minimum number of coins for changing a bigger coin.

``````from typing import List
import sys

def GetNumCoins (coinset : List[int], biggercoin : int) :

mincoins = [sys.maxsize] * (biggercoin + 1)

# 0 is the minimum number of coins needed for changing a bigger coin of value 0
mincoins = 0

for val in range(1, biggercoin+1) :
for c in range(len(coinset)) :
if (val >= coinset[c]) :
mincoins[val] = min (mincoins[val-coinset[c]] + 1, mincoins[val])
val = 0
print ("Value | Minimum Coins")
for c in mincoins :
print(str(val) + "           " + str(c))
val += 1
print (str(mincoins[biggercoin]) + " coins are needed to change the coin of value (" + str(biggercoin) + ")")

def main() :

coinset = [ 1, 4, 9, 16 ]
biggercoin = 10
print ("Coin set : " + str(coinset))
print ("Coin to be changed : " + str(biggercoin))
GetNumCoins(coinset, biggercoin)

if __name__ == "__main__" :
main()
``````

Output

``````Coin set : [1, 4, 9, 16]
Coin to be changed : 10
Value | Minimum Coins
0           0
1           1
2           2
3           3
4           1
5           2
6           3
7           4
8           2
9           1
10           2
2 coins are needed to change the coin of value (10)
``````
``````#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

class Coins {

public:

void GetNumCoins (vector<int>& coinset, int biggercoin) {

const int MAX = 999999999;
vector<int> mincoins(biggercoin+1, MAX);

// 0 is the minimum number of coins needed for changing a bigger coin of value 0
mincoins = 0;

for (int val=1; val<=biggercoin; val++) {
for (int c=0; c<coinset.size(); c++) {
if (val >= coinset[c]) {
mincoins[val] = min( mincoins[val-coinset[c]] + 1, mincoins[val] );
}
}
}

int val = 0;
cout << "Value | Minimum Coins" << endl;
for (const auto& c : mincoins) {
cout << val << "      " << c << endl;
val++;
}
cout << mincoins[biggercoin] << " are needed to change value : " << biggercoin << endl;
}
};

int main() {

Coins c;
vector<int> coinset = { 1, 4, 9, 16 };

int biggercoin = 10;
cout << "Coin set" << endl;
for(const auto& i : coinset)
cout << i << " ";
cout << endl;

cout << "Coin to be changed :" << biggercoin << endl;
c.GetNumCoins(coinset, biggercoin);
return 0;
}
``````

Output

``````Coin set
1 4 9 16
Coin to be changed :10
Value | Minimum Coins
0      0
1      1
2      2
3      3
4      1
5      2
6      3
7      4
8      2
9      1
10      2
2 are needed to change value : 10
``````
``````import java.util.Arrays;
import java.lang.Math;

class Coins {

void GetNumCoins (int[] coinset, int biggercoin) {

int[] mincoins = new int[biggercoin+1];
Arrays.fill(mincoins, Integer.MAX_VALUE);

// 0 is the minimum number of coins needed for changing a bigger coin of value 0
mincoins = 0;

for (int val=1; val<=biggercoin; val++) {
for (int c=0; c<coinset.length; c++) {
if (val >= coinset[c]) {
mincoins[val] = Math.min (mincoins[val-coinset[c]] + 1, mincoins[val]);
}
}
}

int val = 0;
System.out.println ("Value | Minimum Coins");
for (int c : mincoins) {
System.out.println (val + "      " + c);
val++;
}
System.out.println (mincoins[biggercoin] + " are needed to change value : " + biggercoin);
}

public static void main (String[] args) {

Coins c = new Coins();
int[] coinset =  {1, 4, 9, 16};
int biggercoin = 10;

System.out.println ("Coin set");
for (int i : coinset)
System.out.print(i + " ");
System.out.println();

System.out.println("Coin to be changed :" + biggercoin);
c.GetNumCoins(coinset, biggercoin);
}
}
``````

Output

``````Coin set
1 4 9 16
Coin to be changed :10
Value | Minimum Coins
0      0
1      1
2      2
3      3
4      1
5      2
6      3
7      4
8      2
9      1
10      2
2 are needed to change value : 10
``````