Thursday, 11 June 2015

Minimum coins for a given Sum problem

Hello Friends,

Suppose we have infinite amount of coins of certain denominations and we need to find the minimum number of coins required for a given sum.
For this problem if we have coins stored in an array then we need that array to be sorted. Observe how radix sort has been used to sort the array.

public class MinimumCoinChange {
 static Integer coins[] = {2,6,7,1,12,6,1,102,1002,11,100,103,99,1002,1000};
 static int sum = 105;
 public static void main(String[] args) {
  MinimumCoinChange mcc = new MinimumCoinChange();
  int solution = mcc.minimumCoinsRequired();
  System.out.println(solution);
 }
 public int minimumCoinsRequired(){
  int minimumCoinsReq = 0;
  int N = coins.length;
  int[][] ds = new int[N][sum+1];
  radixSort();
  for(int i = 0; i < N; i++){
   for(int j = 0; j < sum+1; j++){
    if(j == 0){
     ds[i][0] = 0; 
    }
    else if(i == 0){
     ds[i][j]= sum/coins[0];
    }else{
     if(j-coins[i]<0){
      ds[i][j] = ds[i-1][j];
     }else{
      ds[i][j]= min(ds[i-1][j],(ds[i][j-coins[i]]+1));
     }
    }
   }
  }
  minimumCoinsReq = ds[N-1][sum];
  return minimumCoinsReq;
 }
 
 public int min(int... a){
  int N = a.length;
  int min = Integer.MAX_VALUE;
  for(int i = 0 ; i < N ; i++){
   if(min>a[i]){
    min = a[i];
   }
  }
  return min;
 }
 public class Node{
  int data;
  Node next;
  Node last;
  public Node(int data, Node next) {
   this.data = data;
   this.next = next;
   last = this;
  }
 }
 public void radixSort(){
  Node[] radixDS = new Node[10];
  int N = coins.length;
  int r = 10;
  int d = 1;
  int remainder,dividend, max = Integer.MIN_VALUE;
  for(int i = 0; i <N; i++){
   if(max<coins[i]){
    max = coins[i];
   }
  }
  boolean isToBreak = false;
  while(true){
   //read all numbers from array to radix DS 
   for(int i = 0; i < N; i++){
    remainder = coins[i]%r;
    dividend = remainder/d;
    if(radixDS[dividend]!= null){
     Node newNode = new Node(coins[i],null);
     radixDS[dividend].last.next = newNode;
     radixDS[dividend].last = newNode; 
    }else{
     radixDS[dividend] = new Node(coins[i],null);
    }
   }
   //read back the data sequentially from radix DS  to array
   for(int i = 0, j = 0; i < 10; i++){
    // it has data, read it in array
    while(radixDS[i] != null){
     coins[j++] = radixDS[i].data;
     radixDS[i] = radixDS[i].next;
    }
    radixDS[i] = null;
   }
   // update the r and d
   r = r*10;
   d = d*10;
   // break
   if(isToBreak){
    break;
   }
   // mark the condition to break
   if(max/r == 0){
    isToBreak = true;
   }
  }
 }
}