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.

9 thoughts on “Greedy Algorithm to find minimum number of Coins | GeeksforGeeks

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

    thanking for modifying it . Great job guys 🙂

  2. 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)

  3. 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;

    }

Leave a Reply

Your email address will not be published. Required fields are marked *