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

Algorithm:

1. If money == 0 then
   1. return 0 because 0 coins required for this.
2. Set min = INFINITY
3. Iterate all coins one by one
   1. If coin value is greater than money then
      1. don’t any thing for this iteration
   2. recursively call (money – coin[i]) money
   3. update min based on recursive call response
4. If min is not INFINITY then
   1. min = min + 1
5. 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

Video

Video