Find the Minimum number of Coins
1) Initialize result as empty.
2) find the largest denomination that is
smaller than V.
3) Add found denomination to result.
Subtract the value of found denomination from V.
4) If V becomes 0, then print result.
Else repeat steps 2 and 3
for the new value of V
Example:
Input: V = 70
Output: 2
We need a 50 Rs note and a 20 Rs note.
C program:
#include <stdio.h>
#define COINS 9
#define MAX 20
// All denominations of Indian Currency
int coins[COINS] = { 1, 2, 5, 10, 20, 50, 100, 200, 2000 };
void findMin(int cost)
{
int coinList[MAX] = { 0 };
int i, k = 0;
for (i = COINS - 1; i >= 0; i--) {
while (cost >= coins[i]) {
cost -= coins[i];
coinList[k++] = coins[i];
}
}
for (i = 0; i < k; i++) {
printf("%d ", coinList[i]); }
return;
}
int main(void)
{
int n;
printf("Enter the Rupees u want Change\n");
scanf("%d",&n);
printf("Following is minimal number of change for %d: ", n);
findMin(n);
return 0;
}
Output:
Enter the Rupees u want Change
1276
Following is minimal number of change for 1276: 200 200 200 200 200 200 50 20 5 1
0 comments:
Post a Comment