# County Money in Greedy Algorithm

Given a value V, if we want to make a change for V Rs, and we have an infinite supply of each of the denominations in Indian currency, i.e., we have an infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins/notes, what is the minimum number of coins and/or notes needed to make the change?

**Examples:**

**Input****:** V = 70
**Output****:** 2
We need a 50 Rs note and a 20 Rs note.
**Input****:** V = 121
**Output****:** 3
We need a 100 Rs note, a 20 Rs note and a 1 Rs coin.

**Solution: **Greedy Approach.

**Approach:** A common intuition would be to take coins with greater value first. This can reduce the total number of coins needed. Start from the largest possible denomination and keep adding denominations while the remaining value is greater than 0.

**Algorithm:**

Sort the array of coins in decreasing order.

Initialize result as empty.

Find the largest denomination that is smaller than current amount.

Add found denomination to result. Subtract value of found denomination from amount.

If amount becomes 0, then print result.

Else repeat steps 3 and 4 for new value of V.

## Example in C++

```
// C++ program to find minimum
// number of denominations
#include <bits/stdc++.h>
using namespace std;
// All denominations of Indian Currency
int deno[] = { 1, 2, 5, 10, 20,
50, 100, 500, 1000 };
int n = sizeof(deno) / sizeof(deno[0]);
void findMin(int V)
{
sort(deno, deno + n);
// Initialize result
vector<int> ans;
// Traverse through all denomination
for (int i = n - 1; i >= 0; i--) {
// Find denominations
while (V >= deno[i]) {
V -= deno[i];
ans.push_back(deno[i]);
}
}
// Print result
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
}
// Driver program
int main()
{
int n = 93;
cout << "Following is minimal"
<< " number of change for " << n
```