# Greedy Algorithm to find minimum number of Coins | GeeksforGeeks

Hi friends! Welcome to Geeksforgeeks. This

is a tutorial for the greedy algorithm to find the minimum no. of coins

Let’s look at the problem statement. Given a value V, we want to make change for V Rs.

We have infinite supply of each of the denominations in Indian currency.

i.e., we have infinite supply of 1, 2, 5, 10 and so on valued coins/notes, what is the

minimum number of coins or notes needed to make the change for V Rs? Let’s look at

an example and this will get clear Suppose the input value is 70. In this case

the output will be 2 and we will need a 50 Rs note and a 20 Rs note.

For the input value 121, the output will be 3 and we will need a 100 Rs note, a 20 Rs

note and a 1 Re coin. Now, let’s look at the solution

We start from the largest possible denomination and keep on adding the denominations while

the remaining value is greater than 0. Let’s see what this means

Basically, we have a result set which we initialise as empty

Next, we find the largest denomination that is smaller than V

Add this denomination to result and subtract the value of this found denomination from

V. If V becomes 0, then print result. Else we

repeat the above steps for the new value of V. Let’s look at an illustration

The input value is 70 and the result set is empty

Now, we check the denominations 1,2,5,10,20,50,100. 100 is greater than 70.

So, 50, which is just lesser than 70, we push it in the result set and the new value will

become 70-50=20 So basically our new value is 20 and the result

set has 50 in it. Again we check the denominations: 1,2,5,10,20.

We found 20 which is equal to the value. So push 20 in the result set and the new value

will become 20-20=0 So the value is 0 and the result set is 50,20

and since the value is 0, we will print the result and no need to repeat the algorithm.

So the input value is 70, the output is 2 and we will need a 50 Rs note and a 20 Rs

note. Now let’s look at the implementation of

this algorithm. First we initialise our result as a vector ans. Then starting from the end,

we traverse through all the denominations and find the denomination which is just lesser

than V. Then simply subtract the value of that denomination from V and push it to the

ans. Note that this while loop will not end until V becomes 0. Once V become 0 and we

exit from the while loop, we will be done. After that we will simply print the result.

Now let’s look at the time complexity of the algorithm. The worst case is that the

denominations array has just one value-1. In this case, the outer fall loop will get

executed just once and the inner while loop will get executed V times. Hence, the time

complexity will be O(V). Now here’s a word of caution. This approach

may not work for all denominations For example, it doesn’t work for denominations

{9, 6, 5, 1} and Value=11. The above approach would print 3 giving 9, 1 and 1. But we can

use 2 denominations 5 and 6. For general input, we use dynamic programming

approach. This will be covered in another video

Thanks for watching! Please leave us your likes and comments.

though my comment was removed , I am happy to see the change in the time complexity now .

thanking for modifying it . Great job guys ðŸ™‚

Say my denomination array was {4,10,25} and I wanted change for a value of 41. How would that work?

we can use binary search to find the greatest denomination value less than the specified value.

when I see Rs.1000 in 0:20 ðŸ¤£ðŸ˜‚

she has used basically word 10 times .

best way of implementing this:

res = V/1000 + (V%1000)/500 + ((V%1000)%500)/100 +….+((((((((V%1000)%500)%100)%50)%20)%10)%5)%2)

with time complexity : O(1)

CAN ANYONE GIVE ME ANY SUGGESTION ABOUT MY PROGRAM ON THIS QUESTION IN C++;

#include <iostream>

using namespace std;

int main()

{

cout<<"enter the money value"<<endl;

int x,coins=0;

cin>>x;

int c[9]={1,2,5,10,20,50,100,500,1000}

for(int j=0;x>0;j++)

{

if(x>=c[8-j])

{

coins++;

x=x-c[8-j];

j=0;

continue;

}

}

cout<<"the number of coins req.="<<coins<<endl;

}

why are u using vector can't we use list there?

@Geeksforgeeks if I have set of {1,9,5,6} and I want 11rs …Then how this solution will work?