Sunday 25 August 2013

coin change problem in java dynamic programming

coin change problem


Given an amount "N" cents, and infinite supply of "1 cent", "2 cent" and "3 cent" coins.

 Your task is to find out
minimum coins required to make change of amount "N cents"
.......................................................................................................................................................................................................


Dynamic programming


class change{
int coin[] = new int[]{1,2,3};
void minCoin(int amount){
int n = mincoin(amount);
System.out.println(n);

}
int mincoin(int amount){
if(amount<=0)
return 0;
if(amount<=3 && amount>0)
return 1;
return minimum(mincoin(amount-1),mincoin(amount-2),mincoin(amount-3))+1;
}
int minimum(int x,int y,int z){
int min;
if(x>=y && z>=y)
return y;
else
if(x>=z)
return z;
else
return x;


}
}
class coinchange{
public static void main(String args[]){
change myobj = new change();
myobj.minCoin(11);


}
}

4 comments:

  1. You have to write the problem description also

    ReplyDelete
  2. Hey, thank you for pointing it out .
    Problem statement is -:

    Given an amount "N" cents, and infinite supply of "1 cent", "2 cent" and "3 cent" coins. Your task is to find out minimum coins required to make change of amount "N cents".

    ReplyDelete
  3. this blog is very useful for interview preparation

    bcbirendra04@gmail.com

    ReplyDelete