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);
}
}
You have to write the problem description also
ReplyDeleteHey, thank you for pointing it out .
ReplyDeleteProblem 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".
this blog is very useful for interview preparation
ReplyDeletebcbirendra04@gmail.com
@Birendra thank you :)
Deletegod bless you.