### Minimum number of coin

##### Given an infinite number of different denomination, calculate minimum coins required to representing n amount.

**Solution:**

- It is based on one simple fact
- Suppose we have following denomination coins
- c0 < c1 < c2 < c3 …….. <cN-1
- Min Coin required for money M (i.e C(m) )
- Cm = min of {C(m-c0) + C(m-c1) + C(m-c2)+ ……. + C(m-cn-1) } + 1

- Suppose we have following denomination coins

##### Algorithm:

- If money == 0 then
- return 0 because 0 coins required for this.

- Set min = INFINITY
- Iterate all coins one by one
- If coin value is greater than money then
- don’t any thing for this iteration

- recursively call (money – coin[i]) money
- update min based on recursive call response

- If coin value is greater than money then
- If min is not INFINITY then
- min = min + 1

- return min

Latest Source Code:

Github: MinimumCoinForChange.java

**Output:**

Min Coin required of 1 :1 Min Coin required of 5 :1 Min Coin required of 7 :2 Min Coin required of 17 :4