Minimum number of Coins

 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