Minimum Coins | Greedy Algorithms

[@mohdirfanmahir3384]

GFG has changed the test cases and this problem can't be done with Greedy anymore. You might consider adding it to DP problems

[@helloworld-uv5os]

how to know if the problem can be solved greedily?

[@bhushandhammrakshit6391]

@takeUforward What to do here ?

[@RohitSingh-du8jx]

​@@helloworld-uv5osyou can dry run it

[@PRINCE-pt5gx]

@@helloworld-uv5os Hey bro sorting is not solving problem here .... let's consider an example to illustrate inefficient coin selection. Suppose you have the following set of coins: [1, 3, 4] and you need to make up an amount of 6. With inefficient coin selection, you might repeatedly choose the largest coin less than or equal to the remaining amount. Let's see how the earlier code would handle this: Initial amount: 6 Largest coin less than or equal to 6 is 4, so you would select one 4 coin and reduce the amount to 2. Remaining amount: 2 Largest coin less than or equal to 2 is 1, so you would select two 1 coins and reduce the amount to 0. So, with inefficient coin selection, you would use a total of 3 coins (1 + 1 + 4) to make up the amount of 6. However, this is not the optimal solution. The optimal solution for this example is to use two 3 coins, resulting in a total of 2 coins (3 + 3).

[@RadheRadhe-w1w3g]

@@helloworld-uv5os just see the topics tag

[@deveshjoshi5627]

hi striver, As far as I have done this sheet there are many good ques which not only are informative but also forms a base for other problems. But i think in this case this question could not be done by greedy. Here is a example for that - let suppose we have V=11 and array as [9,6,5,1] by your method the answer will be 3 as we will first be taking 9 and then 1 two times. But in real case for the minimum coins we must take 6 and 5 which will bring count to 2. That is what I want to tell cause some of the people don't have other resource and they might get confused.

[@RajatGupta-lq3cb]

Exactly.

[@akanshasaxena2472]

First of all this solution is only valid for Indian Rupees i guess. Second thing is you can go for Recursive approach for finding all ways and then get the way which gives you the minimum. But greedy works for Indian Currency as far as I know.

[@yeswanthh5068]

The greedy approach is only valid when all the denominations are increasing in uniform manner😀

[@dhanrajbhosale9313]

correct, Greedy method won't work here. We require DP approach, top down or bottom up kzbin.info/www/bejne/fmrFl6Slr8-ip9U

[@aayushrajput1261]

@@yeswanthh5068 what do you mean by uniform manner ?? 1,2,5,10 how is this uniform??

[@fawazwangde9091]

Hy striver i hope you are doing extremely well😀....I would like to bring it to your notice that the practice link 2 in the sheet is pointing to a different problem....

[@VipinKumar-us1sr]

time complexity can be further reduced, instead of using while loop we can say that for den[i] , its number of coins will be V/den[i] and the do V -= ((V/den[i])*den[i]) ;

[@pekkingjackal1180]

Can you explain the logic behind this formula??

[@sudhanshugupta9692]

We can use this formula to decrease the time complexity. But it would be useful when just the number of coins is asked. Here, you need to print the combination/sequence. Therefore, the loop has to run in this case!

[@shinei9459]

@@pekkingjackal1180 he is using factors once it gives you the quotient that is the number of coins say for example you have amount 21 and use 5rs coin in total u get 21/5 i.e 4 coins then you subtract 4*5 from the amount that gives you the remaining I hope you get the logic now :-)

[@karanprabhakar72]

@@shinei9459 Please find the code int findMinimumCoins(int amount) { vector arr = {1, 2, 5, 10, 20, 50, 100, 500, 1000}; int quo = 0; for(int j = arr.size()-1; j >=0 ; j--) { if(arr[j]

[@jigarshah7434]

so new value=v%arr[i] and no of coins = v/arr[i] right ?

[@ajayjangid1164]

Imp Notepoint:- Greedy approach only works if test cases are such that (sum_of_prefix_array < current_element). Or i.e sum(coins[0] to coins[i-1]) < coins[i];

[@godofwar1260]

what if test case is [5,10,21] and amount is 30? 5+10

[@reverbmusic8444]

@@godofwar1260 bruh why you taking 5+5+10+10 we can directly take 10+10+10

[@shubhams5121]

@@reverbmusic8444 By greedy 21 will be taken first leaving out 9.

[@mohitagrawal8500]

This question can't be done by greedy, consider the case where V = 30 and arr = [25,10]. We need to use DP to solve this problem.

[@iamnottech8918]

that.s what he said val are decided in a way such that sum of prev 2 is smaller than next for greeddy to work hereindeed dp will be used

[@Clutchgod-l9z]

what's a DP?

[@Clutchgod-l9z]

@@mohitagrawal8500 answer me

[@nihilantech1986]

​@@Clutchgod-l9zDynamic programming Bro

[@iamstudying389]

for anyone who is confused there are two such questions, the linked quesiton in sheet is with random denominations. this method will only work if all the bigger denominations are multiples of every smaller denominations. because then we wont have to take the case of suppose: 80 with denominations 25 and 10. 75+5 NO ::: 50+ 30 yes ..if 25 was multiple of 10 then we are bound to fully use 25 because if we not , more number of 10s will be used as 25 is a multiple of 10 so better to use 25 only. but this is not the cas ei n random denominations

[@abhimanyu6534]

This method only works for indian currency ? If not in which other cases it can be used on gfg the same ques is having the exact case that you showed but it fails with greedy

[@sharath5796]

Python Code: denominations = [1, 2, 5, 10, 20, 50, 100, 500, 1000] def findMinimumCoins(amount): count=0 for i in range(len(denominations)-1,-1,-1): while denominations[i]

[@stith_pragya]

Understood......Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@nonamenigha]

Hi Striver bro, are these SDE sheet problems enough to prepare for college campus placement interviews?

[@takeUforward]

If you take concepts, should be enough if know basic DSA..

[@Rajat_Dhasmana]

Instead of subtracting the denomination multiple times, we can do a floor division Here is my python solution for same, denominations = [1, 2, 5, 10, 20, 50, 100, 500, 1000] def findMinimumCoins(amount): d = denominations i = len(d) - 1 totalCoins = 0 while i >= 0 and amount > 0: coins = 0 if d[i]

[@roushanraj8530]

Bro, you are not in stage to even speak properly, yet you are making videos only for us, you are just awesome 💥💯💯💥

[@takeUforward]

Areh aisa nai hai, I am getting super bored by doing nothing, so just making some videos so that my time goes well...

[@roushanraj8530]

@@takeUforward ohkk brother, watch some good series on Netflix and chill 😍, and make videos also if it is comfortable

[@roushanraj8530]

Implementation of BFS using stack ni mil rha kahi pr v, BFS using Queue and DFS using Stack hi mil rha h aisa q ....?, please bhya help

[@indiansoftwareengineer4899]

@@takeUforward bhai, sahi idea he time bitane ka, ye youtube toh tumhe hobby ki tarha he na...

[@yutaitadori7318]

@@takeUforward 🥺 thank you so much 😭

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks striver for the video... :)

[@sanskarmaliwad4240]

Instead of using while loop can we update v=v%deno[i] ??

[@Rajat_Dhasmana]

The modulo will give us remainder, we are interested in the divisor so floor division would be suitable.

[@reee896]

I THINK INSTEAD OF SUBSTRACTING EACH TIME WE CAN FIND THE QUOTIENT AND MULTIPLY IT WITH THAT VALUE AND REMOVE FROM THE COUNTER SUM

[@beingvoid3246]

Code using binary search : class Solution{ public: vector minPartition(int N) { vectorden = {1,2,5,10,20,50,100,200,500,2000}; vectorans; while(N > 0){ auto it = lower_bound(den.begin(),den.end(),N); int idx , cnt; if(it != den.end()){ if(*it != N) it --; idx = it - den.begin(); }else idx = 9; cnt = N / den[idx]; N -= cnt * den[idx]; while(cnt --) ans.push_back(den[idx]); } return ans; } };

[@aniruddhakotal1534]

but in the question, They have given there set of coins, so it can be easily done with DP, not with greedy

[@paragroy5359]

Thanks for the sde sheet and the playlist it is really helpful...

[@prashantgupta808]

Good work, btw whay are you doing ? I mean a student or doing some job?

[@takeUforward]

Check the about section of the channel..

[@jakeperalta8135]

Will the c++ code given at the end work when we have to take more than 1 coin of same value?

[@takeUforward]

Yeah there is a while loop

[@AnshKumar-dp1st]

sum=20 coins[ ]= 1 4 16 17 this test case will give 4 as answer, but minimum no. of coins required is 2.

[@yatharthahuja1635]

4 and 16

[@rishika6525]

thanks a lot for also explaining why recursion is not required here

[@Leet_Lords]

Note: Sort the array first then iterate from n-1 index

[@karanamdharneesh4279]

does greedy fails if we consider different array of coins?

[@TheBaljitSingh]

Greedy not work because of these Test case, have to Implement the DP(doing it with simple recursion take and not take approach might lead to TLE) : test case: coins = [2,3] , amount = 4

[@sumitchakraborty9451]

striver vaiya i completed your sde sheet; what should i practice now??

[@shshnk11]

Hey Striver, what about a test case like [1, 5, 7] and amount = 10. Here greedy doesn't work even when sum of 2 smaller denominations doesn't exceed the larger denominations. How to know if greedy works or not?

[@navinchandra5361]

See, in your example 5+5=10 which exceeds 7, hence greedy cannot be applied. In case of denominations the sum may be equal but not greater thus, we can use greedy (10+10=20, 20 note is also there but it doesn't exceeds sum of two 10's!)

[@zealkapadiya4783]

Thankyou for covering this hard problem!!😀

[@takeUforward]

Areh, I know its an easy one, but am just following the SDE sheet...

[@zealkapadiya4783]

@@takeUforward There is another coin change problem on leetcode which is hard...this one was relatively easy

[@anmollalit]

But your explanation does not work for this test case [1,6,8] V=12, Here if we take greedy algorithm, then we would have 8 1 1 1 1 as solution which is wrong solution would come from 6 6, here neither their sum is greater than other denomination, like in the case of [1,5,6,9].

[@godofwar1260]

Only works for Indian currency

[@shuaibkhan5224]

You are doing great work ,Hats of you 🙌🏻

[@Akash-e8v4n]

for (int i = n - 1; i >= 0; i--) { while (V >= coins[i]) { V -= coins[i]; ans.push_back(coins[i]); } } Time complexity = O(V) but what about the outer loop we have

[@aabhassaxena2490]

It will also fail for Deno: 2 5 Sum: 8 Why?

[@takeUforward]

8 cannot ne made :P the minimum coins only work for given denominations..

[@impatientgaming9868]

really nice explanation

[@harikrushnasuhagiya3925]

You are doing great work ,Hats of you

[@bstcoder2088]

bro i learnt a lot of things from your this video thanks for making this type of help full video😀

[@devrajgoswami4357]

I hate this KZbin community for Not letting him grow faster :"-(

[@Yomanthunder-e4c]

this code is not correct ?

[@rakeshrajput537]

It's wrong. take an example 9 6 5 1 to make 11, by your approach 3 coins needed while ans will be 2(6,5);

[@little-by-little-one-trave1770]

Yes It should be solve through DP

[@joydeb8202]

Striver you are great.. Thanks for this... Brother

[@rishabhkukreja6910]

Great work bhaiya 1 cheez batado ki dbms and os ki puri playlsit dekhni h knowledge gate ki bcoz 150 videos h and unme thode topics bhi missing hai shyad ? (Asking Specifically for placement)

[@HARIHaran-ks7wp]

249 likes. *0 dislikes* Power of Striver bhai!!

[@sargamagarwal4544]

That test case failing part was 🔥

[@maestro11111]

Why if the pair sum never exceeds later coins (2, 5 never exceeds 10), works in case of greed?

[@godofwar1260]

Even that condition won't work. what if test case is [5,10,21] and amount is 30? 5+10

[@opanpro9772]

I would like to draw your attention striver to the fact that this solution is wrong actually. It won't work for this case: when deno = { 1, 5, 6, 9 } where V = 11. This can't be solved using greedy approach.

[@architchandrakar1286]

He mentioned that in the video @7:36 along with the fact that it can be solved using DP.

[@godofwar1260]

Only works for Indian currency

[@souvikmukherjee8533]

Below is the code for greedy but doesnt work anymore as GFG stopped supporting greedy for this question. now modified to a DP question. #include using namespace std; void solve(){ int n; cin>>n; int v; cin>>v; vector res; for(int i=0; i>x; res.push_back(x); } int count = 0; while(v>0){ for(int i=0; i

[@himalayagupta7744]

a better solution very similar to integer to roman question on leetcode vector coins{1,2,5,10,20,50,100,200,500,2000}; vector ans; while (N != 0){ if (N >=1 && N < 2){ ans.push_back(1); N -= 1; }else if (N >=2 && N < 5){ ans.push_back(2); N -= 2; }else if (N >=5 && N < 10){ ans.push_back(5); N -= 5; }else if (N >= 10 && N < 20){ ans.push_back(10); N -= 10; }else if (N >= 20 && N < 50){ ans.push_back(20); N -= 20; }else if (N >= 50 && N < 100){ ans.push_back(50); N -= 50; }else if (N >= 100 && N < 200){ ans.push_back(100); N -= 100; }else if (N >= 200 && N < 500){ ans.push_back(200); N -= 200; }else if (N >= 500 && N < 2000){ ans.push_back(500); N -= 500; }else if (N >= 2000){ ans.push_back(2000); N -= 2000; } } return ans;

[@ashutoshtripathi8257]

Thanks bhaiya ♥️♥️

[@shy6489]

what about test cases when arr[]={1,3,4,5} and n=7 then by your approch ans is 5,1,1 (i.e .3 coins); but correct answer is 3,4 (i.e. 2 coins);

[@riddhibandyopadhyay584]

start watching from 7:00 you will get it

[@shy6489]

@@riddhibandyopadhyay584 👍

[@shivanshgupta7165]

We need to sort the array too , so tc will be nlogn

[@helloworld-uv5os]

how to know if the problem can be solved by greedy technique?

[@rushabhlegion2560]

I think the following code is more optimized int findMinimumCoins(int amount) { int ans=0; while(amount){ if(amount>=1000) amount-=1000; else if(amount>=500) amount-=500; else if(amount>=100) amount-=100; else if(amount>=50) amount-=50; else if(amount>=20) amount-=20; else if(amount>=10) amount-=10; else if(amount>=5) amount-=5; else if(amount>=2) amount-=2; else amount-=1; ans++; } return ans; }

[@ppg3530]

Thanks 👍🏻👍🏻👍🏻

[@yeswanthh5068]

Thank you sir understood

[@sawantanand3681]

i think it will fail for some cases like 47 and many more

[@anjandey6089]

coins arr= [1,15,25] , amount = 30 greedy -> 6 and dp gives -> 2. why greedy is not work here? as per your logic (1+15)

[@takeUforward]

twice of 15 should be greater than 25 also .. it does not satisfied, if you carefully see

[@godofwar1260]

​@@takeUforward Even that condition won't work. what if test case is [1,5,10,21] and amount is 30? 1+5

[@indiansoftwareengineer4899]

Hey bro, you have comeback... You have great passion for Teaching.... Loved your efforts..

[@KishanPatel-nd3yb]

I have question what makes the coins values so special that greedy algorithm work ? Like given a general problem looking at the coins values how can we judge the optimal solution DP Vs Greedy ? In cormen book they have mentioned some concept of matroids for greedy solutions but I didn't understood that ? anyone could explain me this ?

[@SunilSharma-mb2kf]

Explanation is at 7:00

[@anonymoussloth6687]

@@SunilSharma-mb2kf the explanation is wrong. If i have coins {1,3,4} 1+3 doesn't exceed 4 but greedy fails if u try for 6. Greedy will give 4+1+1 but optimal answer is 3+3

[@varunsharma5582]

@@anonymoussloth6687 Yupps, this question can't be solved with greedy.

[@anonymoussloth6687]

@@varunsharma5582 so what's the actual reason why it can't be solved by greedy?

[@varunsharma5582]

@@anonymoussloth6687 Greedy will consider a coin to be part of the solution then later you'll discover that the coin can't be part of solution and you'll need to skip it. Hence, you need to check all the combinations, which means it becomes a 0-1 knapsack problem anyways and you'll end up using dp

[@shashankkumarsingh6516]

Great explaination

[@HARISHKUMAR-tt6ji]

Bro could you put some videos on kmp algorithm

[@takeUforward]

Yes, I will as the SDE sheet sequence goes.. I won't be jumping since it then creates a very bad playlist structure..

[@dreamyme543]

Thank you striver:)

[@sagarsuman1299]

Boom not valid for all the coin sets : practice.geeksforgeeks.org/problems/number-of-coins1824/1#

[@bhaveshkumar6842]

Thank you, Striver for explaining everything so clearly.

[@lakshmiprasanna7058]

Understood 💯💯💯

[@Pandurang_25]

bro if array is not sorted then how this method will work?

[@kumarankit5726]

sort it,also this code works only for the given coins{1,2,5,10,20,50,100,500,1000}

[@neyovyas3992]

Aap apna code bhi dikhao na last me vo samajtha hai gfg pe nahi samajhte

[@takeUforward]

pura dekh lia kro video, code last me humesha rhta !!

[@neyovyas3992]

@@takeUforward koi koi me nahi rehta isliye but thank you ab rehta hai

[@neyovyas3992]

Thank you bro

[@takeUforward]

Welcome

[@jinhuang7258]

Understood.

[@mohammedelhag7565]

thank you, sir

[@AmanKhan-bw3rt]

Today I understood the reason of money denomination hehhe

[@siddharthmishra8012]

It would fail for 1 5 6 9 For sum =11 Please confirm

[@limakbear7029]

Then we should use Dynamic Programming

[@amirghorban2044]

Awesome god bless you

[@NARUTOUZUMAKI-bk4nx]

Understood

[@MJBZG]

understood

[@priyanshvatsal9791]

Understood😇

[@ambrish8144]

Problem link

[@takeUforward]

Description

[@deweshjha8120]

@@takeUforward nahi hai bhaiya.

[@activeperson1799]

I guess U won't listen to us. Please take some rest 🙏🙏 I am not saying this for any formality brother

[@searchapostateprophetabdul2398]

He replied to some person that actually he was getting bored just lying down in bed all day.

[@takeUforward]

Areh baithe baithe bore ho rahe brother, cannot just be not doing nothing.. I am taking care while making this video..

[@harshyadav6097]

solution is wrong as per the given question

[@MJBZG]

appreciate your efforts striver but by making your previous playlist private, you have really really ruined the experience for me. i spent two months watching those videos making notes and gettoing accustomed to them now when i have to revise, i have to watch a new video all over again. Expected better, really.

[@yashgarg8906]

awesome

[@kartikdalai7998]

target = 21 and coins [9,6,5,1] your code out put is -> 5 expected and -> 4

[@052_a_sourabhpathak5]

ArrayListds=new ArrayList(); int arr[]={1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}; int n=arr.length; int money=N; for(int i=n-1;i>=0;i--){ if(arr[i]>money)continue; else if(arr[i]

[@PankajKumar-ps5gg]

int findMinimumCoins(int amount) { // Write your code here int coins[] = {1000, 500, 100, 50, 20, 10, 5, 2, 1}; int i = 0; int counts = 0; while(amount>0) { if(amount>=coins[i]) { int c = amount/coins[i]; counts += c; amount -= c*coins[i]; } i++; } return counts; }

[@vedantbothikar]

understood