@@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).
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.
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.
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....
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]) ;
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!
@@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 :-)
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];
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
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
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]
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
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?
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!)
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
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 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
@@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
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.
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].
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
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;
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)
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.
GFG has changed the test cases and this problem can't be done with Greedy anymore. You might consider adding it to DP problems
how to know if the problem can be solved greedily?
@takeUforward What to do here ?
@@helloworld-uv5osyou can dry run it
@@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).
@@helloworld-uv5os just see the topics tag
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.
Exactly.
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.
The greedy approach is only valid when all the denominations are increasing in uniform manner😀
correct, Greedy method won't work here. We require DP approach, top down or bottom up ua-cam.com/video/H9bfqozjoqs/v-deo.html
@@yeswanthh5068 what do you mean by uniform manner ?? 1,2,5,10 how is this uniform??
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....
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]) ;
Can you explain the logic behind this formula??
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!
@@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 :-)
@@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]
so new value=v%arr[i] and no of coins = v/arr[i] right ?
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];
what if test case is [5,10,21] and amount is 30? 5+10
@@godofwar1260 bruh why you taking 5+5+10+10 we can directly take 10+10+10
@@reverbmusic8444 By greedy 21 will be taken first leaving out 9.
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.
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
what's a DP?
@@mohitagrawal8500 answer me
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
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
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]
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]
Hi Striver bro, are these SDE sheet problems enough to prepare for college campus placement interviews?
If you take concepts, should be enough if know basic DSA..
Instead of using while loop can we update v=v%deno[i] ??
The modulo will give us remainder, we are interested in the divisor so floor division would be suitable.
Understood......Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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;
}
};
Bro, you are not in stage to even speak properly, yet you are making videos only for us, you are just awesome 💥💯💯💥
Areh aisa nai hai, I am getting super bored by doing nothing, so just making some videos so that my time goes well...
@@takeUforward ohkk brother, watch some good series on Netflix and chill 😍, and make videos also if it is comfortable
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
@@takeUforward bhai, sahi idea he time bitane ka, ye youtube toh tumhe hobby ki tarha he na...
@@takeUforward 🥺 thank you so much 😭
UNDERSTOOD... !!!
Thanks striver for the video... :)
sum=20
coins[ ]= 1 4 16 17
this test case will give 4 as answer, but minimum no. of coins required is 2.
4 and 16
Will the c++ code given at the end work when we have to take more than 1 coin of same value?
Yeah there is a while loop
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
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?
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!)
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
It will also fail for
Deno: 2 5
Sum: 8
Why?
8 cannot ne made :P the minimum coins only work for given denominations..
thanks a lot for also explaining why recursion is not required here
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 ?
Explanation is at 7:00
@@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
@@anonymoussloth6687 Yupps, this question can't be solved with greedy.
@@varunsharma5582 so what's the actual reason why it can't be solved by greedy?
@@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
I THINK INSTEAD OF SUBSTRACTING EACH TIME WE CAN FIND THE QUOTIENT AND MULTIPLY IT WITH THAT VALUE AND REMOVE FROM THE COUNTER SUM
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)
twice of 15 should be greater than 25 also .. it does not satisfied, if you carefully see
@@takeUforward Even that condition won't work. what if test case is [1,5,10,21] and amount is 30? 1+5
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);
Yes It should be solve through DP
I hate this UA-cam community for Not letting him grow faster :"-(
Thanks for the sde sheet and the playlist it is really helpful...
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);
start watching from 7:00 you will get it
@@riddhibandyopadhyay584 👍
Good work, btw whay are you doing ? I mean a student or doing some job?
Check the about section of the channel..
Why if the pair sum never exceeds later coins (2, 5 never exceeds 10), works in case of greed?
Even that condition won't work. what if test case is [5,10,21] and amount is 30? 5+10
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.
He mentioned that in the video @7:36 along with the fact that it can be solved using DP.
Only works for Indian currency
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].
Only works for Indian currency
does greedy fails if we consider different array of coins?
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
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;
Note: Sort the array first then iterate from n-1 index
striver vaiya i completed your sde sheet; what should i practice now??
but in the question, They have given there set of coins, so it can be easily done with DP, not with greedy
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)
Thankyou for covering this hard problem!!😀
Areh, I know its an easy one, but am just following the SDE sheet...
@@takeUforward There is another coin change problem on leetcode which is hard...this one was relatively easy
how to know if the problem can be solved by greedy technique?
i think it will fail for some cases like 47 and many more
bro i learnt a lot of things from your this video thanks for making this type of help full video😀
You are doing great work ,Hats of you
Striver you are great.. Thanks for this... Brother
249 likes. *0 dislikes* Power of Striver bhai!!
It would fail for
1 5 6 9
For sum =11
Please confirm
Then we should use Dynamic Programming
Hey bro, you have comeback...
You have great passion for Teaching....
Loved your efforts..
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;
}
That test case failing part was 🔥
We need to sort the array too , so tc will be nlogn
bro if array is not sorted then how this method will work?
sort it,also this code works only for the given coins{1,2,5,10,20,50,100,500,1000}
Thank you, Striver for explaining everything so clearly.
this code is not correct ?
You are doing great work ,Hats of you 🙌🏻
Aap apna code bhi dikhao na last me vo samajtha hai gfg pe nahi samajhte
pura dekh lia kro video, code last me humesha rhta !!
@@takeUforward koi koi me nahi rehta isliye but thank you ab rehta hai
Bro could you put some videos on kmp algorithm
Yes, I will as the SDE sheet sequence goes.. I won't be jumping since it then creates a very bad playlist structure..
Thanks bhaiya ♥️♥️
Great explaination
Thank you sir understood
Boom not valid for all the coin sets : practice.geeksforgeeks.org/problems/number-of-coins1824/1#
Thank you striver:)
Today I understood the reason of money denomination hehhe
Awesome god bless you
I guess U won't listen to us.
Please take some rest 🙏🙏
I am not saying this for any formality brother
He replied to some person that actually he was getting bored just lying down in bed all day.
Areh baithe baithe bore ho rahe brother, cannot just be not doing nothing.. I am taking care while making this video..
Thank you bro
Welcome
solution is wrong as per the given question
Understood 💯💯💯
Thanks 👍🏻👍🏻👍🏻
thank you, sir
Problem link
Description
@@takeUforward nahi hai bhaiya.
Understood.
Understood😇
Understood
understood
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.
awesome
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]
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;
}
understood