### count number of coins

Given a list of 3 coins, their values (1,3,5), and the total sum 11. Find the minimum number of coins the sum of which is 11 (we can use as many coins of one type as we want).

Hint: use dynamic programming

1. int count_coins(int * coin,int len,int money)
{

int arr[100];
for(int i=0;i<100;i++)
{
arr[i]=999;
}
arr[0]=0;
for(int i=0;i<=money;i++)
{
for(int j=0;j=0)
{
arr[i]=min(arr[i],1+arr[i-coin[j]]);

}
}

}

return arr[money];
}

2. typo error for 2nd loop: for(int j=0;j<len;j++)

3. @ankit why initially you have taken array of 100 elements...

4. @priyaranjan ... ummmm lazyness i dint want to write
int * arr=(int *)malloc(money*sizeof(int));
;)
so i assumed that maximum money that user wud input is 99

Btw..is the code correct?

1. Hi

Try for S=3. array[5,2,1]
answer shd be 2, it gives 1.

I think before
arr[i]=min(arr[i],1+arr[i-coin[j]]);
if(i>=coin[j])

that wud do!

2. @anonymous please see the below comment, it depicts the same logic..:)

5. @ankit yeah rest logic is correct..:)

6. Set Min[i] equal to Infinity for all of i
Min[0]=0

For i = 1 to S
For j = 0 to N - 1
If (Vj<=i AND Min[i-Vj]+1<Min[i])
Then Min[i]=Min[i-Vj]+1

Output Min[S]