Friends Pairing Problem Dynamic Programming | Explanation with Code
Vložit
- čas přidán 5. 08. 2020
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the Friends Pairing problem where we are required to print the number of ways in which n friends can pair up where each person has two options, either to pair up or to stay single. In this problem,
1. You are given a number n, representing the number of friends.
2. Each friend can stay single or pair up with any of it's friends.
3. You are required to print the number of ways in which these friends can stay single or pair up.
E.g.
1 person can stay single or pair up in 1 way.
2 people can stay singles or pair up in 2 ways. 12 = 1-2, 12.
3 people (123) can stay singles or pair up in 4 ways. 123 = 1-2-3, 12-3, 13-2, 23-1.
To attempt and submit this question, click here: www.pepcoding.com/resources/o...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#dp #dynamicprogramming
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
That's why you Don't have any dislike.... Noobs to advance level programmers all will understand your explanation.
Amazing sir 🙏
Glad you liked it!! keep watching and share among your peers
Absolutely true. Explanation for everyone
I m glad that I have solved this question by only watching the first 3 minutes of the video, these videos are helping me alot
Thanks for your videos....Amazing simple explanation to complex problems!
I tried a lot to think about it. But I didn't. Finally I got this video. And finally I got it. Thank you so much. Most of the CZcamsrs were unable to make this concept understandable. Thank you so much❣️
Best explanation found on CZcams
Thankyou so much Sumit sir , great solution
aweswome explanation sir!!!!
Although i understood ,ur explaination in the first go, but still watched all repeated explaination,even from every angle and insights, salute for your extra enthusiasm in teaching....thank u for outstanding explaination.....
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
Thanks for explaining why we should not take NC2 in the formula, i have seen numerous channels explaining how to solve and stop. You are going one step ahead and explain the common misconceptions/ mistakes students do. Thank you for going the extra mile.
Glad you liked it!
For better experience, visit nados.pepcoding.com, where you will get well curated content and career opportunities.
wow great explainatation sir ........................a beginner student can also understand your teaching methodology.................
Too good as always ❤️👍...
One of the best explanations ever.... Wow!! Thanks a lot sir
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
Great job. Smooth to understand. :)
yahi to chaie
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
czcams.com/users/Pepcodingabout?view_as=subscriber
For clearing your doubts, you can join our community on telegram
t.me/pepcoding
Bettern explanation than GFG. I came here from GFG. Thanks!
Thank you so much for your amazing explaination sir.
Thankyou beta,
I am glad you liked it. I also hope that you are watching till end.
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
next level insights mile isme to .. ,much thanks : )
Wow, thanks!
kitni baar samjhate h ek cheez ko...it show your dedication...thanks alot sir
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
i liked the part where in some solution doesnt work and why they dont work.. It gives me more insight as to what i should not do.. and this is what most of the question required..
Thank you
Nice explanation 🔥🔥🔥
Mast smjhaya teacher
nice explanation
kya bhaval padate ho sir ji !! very interesting was the second part of explanation of why other approach is wrong . sir please is further videos i request you to come up with more such failure cases .
thank you sir
Awesome sir 🔥🔥🔥🔥🔥
maa kasam apni poori life mai iss tareh se hindi mai explanation nahi dekha.
mann toh kar raha hai ki aapki saari videos aaj hi dekh loo
khusi bayan nahi kar sakta .....Thanku Thanku So much sumit sir.
wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.
U R A REAL PEPCODER :)
Thankyou!
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
The best explanation
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
I don't know hindi
But i understood the logic
That much ur explanation is..
Thank u so much
Thanks Buddy!
I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to review us here - g.page/Pepcoding/review?rc
Also, I would like to inform that soon we are going to start the same content in english also.
wow.. amazing explanation .. ek baar mein samajh aa gaya .. sir make videos on daily challanges .. like leetcode monthly challange....
beta oct 30 ke baad bnaunga. Tab tak leetcode level ke normal list planned hai ek
Thank you :)
You're welcome!
you may also make videos in english as there is many audiences those who don't understand hindi properly...by the way a great explanation
Accidentally i solved this question , and accidentally i got the formula also ,
Now , after seeing this video , understood that formula 😂😂😂..
Thank you sir...
ya same happened with me also 😅
Aise he lage rho beta, phle khud he koshish krni chaheye beta, but jab thak jao soch soch k aur solution na smj aaye tab fr le lo help solution video ki
@@Pepcoding yes sir you are absolutely right, thanks for all your efforts and great explanation of these videos, more power to you sir 🙂
Bhai, it's awesome
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Keep learning and keep loving Pepcoding😊
standing ovation from me....legend level explaination
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
@@Pepcoding best videos on ds algo on youtube..pranam swikar kare sir
@@Pepcoding sir ek crash course series v laye
class!!
For better experience and curated content sign up on nados.io and post your queries on community tab of NADOS.
can there be one variationn of this problem where we add the condition of having 3 groups also with single and paired groups
and also what could be the recurrence relation?
Wow after watching this, I realise how easy it was and how difficult I made it.
Thanks sir..
Welcome
Amazing explanation.. 5th grade ke bacche bhi samaj jayenge 😍
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Sir can this be done in O(1) , in such a manner that when we are given n we just insert it in an equation and get the final answer as we already know what series it will follow.
Great explanation
Glad it was helpful! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Ye doubt aya .Apne solve kr diya
wow
❤
sir it will not pass the case when n=100000 ,i have given long dataType but still getting 0 as my output
sir tiles M*1 ques me problem hai
why dp of size n+1 not m+1
when is sumeet sir coming back. also will he be teaching in the NADOS program. please help @Pepcoding
Literally bro kaya samjhaya hai maaza aa gaya aisa mainey apne paid courses me samjha tha aapne uss se bhi upar wale level ka samjha dala 🔥🔥🔥
bhot khushi hui ye sunkar. kaunsa paid course tha?
Ninja
@@anjneykumarsingh4461 bhai tum abhi kaha job kr rahe ho??
@@akshitrawat-gv2bh govt
@@akshitrawat-gv2bh not in IT
Sir after foundation can you parallely start levelup recursion and Interview prep arrays+strings. Since foundation + array string of IP would be helpfull for us to crack small product based companies. Otherwise it will take time to start with arrays after levelup.
Will do it in parallel bro.
Nice explanation
Thanks for liking
Find Largest Area
Given you a box which is separated by line, both horizontally and vertically. Imagine there are n
lines present vertically and m lines are there horizontally (every box created by the lines are 1
unit). Now you have been told to remove some lines from horizontal and vertical. You have to
calculate the largest box created after the changes.
Sample Input:
n=5
m=5
h=[2]
v=[2,3,5]
Output:
6
Nice
Thanks and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Awesome explaination sir🙏
Thanks and welcome. Please share and subscribe as well.
Thanks for liking the content, I request you could write about our channel on your facebook or linkedin? So that maximum students could get the best out of it.
Ok sir,I will
Done sir
lajavab
Thank you.
Awesome
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@@Pepcoding sure 🙂
sir does dynamic programming focus only on counting the number of cases and not exactly getting those cases ?
Aisa nahi hai. Extended question hota hai jisme case bhi btana hota hai. DP + Graphs se hoga. Hum krenge.
your video force me to give a thumbs up.
Keep watching and keep loving Pepcoding😊
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
@@Pepcoding I love to.
Bhaiya 1 video , for loops and nested for loops ki time complexity pe bna dijiye
bro, time and space mei abhi 10 videos aur daalni hain.
Sir pls make video on N/3 repeated number in an array with O(1) space
Sure. Soon.
👌
Jai Hind Beta
Sir.. If you please increase duration of video.. to say 40-45 minutes.. in dynamic programming. It will become most helpful.. as recursion then memorisation then tabulation.. It will be most helpful...
beta dp via recursion alag se karunga.
I did is slightly different.
public static int friendsPairing(int n) {
int single = 1;
int pair = 0;
for(int i=2;i
submit it and see if all the test case pass else rfer this solution
int single = 1;
int pairUp = 1;
int ans = 0;
for (int i = 2; i
you have done right , har ek banda kitne tareeko se single raha sakta hai is , kitne tareeko se baki bache log pair up ya single rah sakten hain, . ab ek banda kitne tareeko se pair up kar sakta hai is ki voh kisi bhi ek bande ko pakad le aur pair up hojaye , aur ab baki bache n-2 log kitne tareeko se pair up ya single rahne ka game khel sakten hain.
public static int friendsPairing(int n) {
int a = 1; // i have stored the number of ways 1 person can remain single or pair up
int b = 2; // i have stored the number of ways 2 person can remain single or pair up
int total=0 // total no of ways i th person can remain simgle or pair up
for(int i=3;i
In the question constraint is given as 0
sumit sir is god
sir aap bata rahe the ki dp via tabulation is better than recursion...why?@PepCoding
kyunki isme aapko topological sort sochna padta hai aur memoization mei nahi sochna padta. is point pe vichar kijie.
💞💞💞
keep motivating, keep learning and keep loving Pepcoding😊
I am able to understand the problem but I am not able to solve them on my own before seeing the explanation. Is this a problem? How should I overcome it(I have solved 100+ problems from pepcoding)
sir ismei 3 ka pair allowed hai , like if we have 4 friends then 134, 123, 124, jaise case allowed honge ?
3 ka triplet hoga na, pair to 2 ka he hota hai.
Excellent explanation sir just a small doubt that when we are calling recursion on f(n-1) means when we are not including 1 as a pair
Why don't we add 1 + f(n-1)? Because we should count 1 naa even if we are not including it.
❤️❤️❤️❤️
keep loving Pepcoding😊
@@Pepcoding always 💻❤️
Python code for above problem
def compute(n):
dp = [0] * (n+1)
for i in range(n+1):
if i
sir 3-4 hardest problems daal do please please like google interview very new type of hard problems
Bhot jaldi aa rhe hain. Levelup ka backtracking bhot alag hoga, leetcode se geeksforgeeks se. Sabse alag.
@@Pepcoding thank u so much , faad faad que daal do interviews are going on ,that will be helpful
why cannot 1,2,3 be together?
This code will fail if n=1,coz dp=new int [n+1],it will create a size of 2 , and dp[2] will not exist . so make dp[0]=1 and dp[1]=1 and start for loop with i=2
bhaiye N=6569 kay liye galat aa rha hai 0 aa rha hai
8 disliker are other youtube coder😂😂😂😜just Kidding
And I'm like that bchha😂,
But on getting error i turn to chellam sir of dp😁😂
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Sir is ques m tabulation ni use kra h .
I am confused ki recursive approach use kru ya tabulation anyone pllz help🙏
koi bhi use krr le bhai..same hi hain dono.
@@raghurajpratap5015 bhai tabulation s itna clear ni ho para
So what i am asking hume phle konsi approach try krni h recursive ya tabulation
Hmesha apko phle brute force approach se start krna chaheye.
@@Pepcoding ok that's mean we have to start with recursion then go to dp
Tq so much sir ☺ 🙏
dp[3] = 4
ye rkh kr bhi pass ho rha hai
!!!!!!!
The crux of the video 7:00
Sumeet Bhaiyya foundation khatam ?
DP - 5 videos more (or 25 based on mood, if they don't come in foundation they will in levelup)
Graph - 20 videos
OOPs - 15 videos
Time and Space - 10 videos
Strings, SB and ArrayList - 10 videos
@@Pepcoding sir i request you..plss post 25 videos of dp..first in foundation only..plss sir ...placement tym is going on..i really need your videos.u r a life saviour..
please sir videos thodi choti banayo
Badi videos me hum aapko indepth knowledge de paate jo product based companies me important hoti hai
in "12" there is 2 pair (1) -> 1-2 (2) -> 12.
in "123" we count (1) 1-2-3 (2) 1-23 (3) 12-3 (4) 13-2
why 123 is not a pair there should be 5 ways to pair up (5) 123
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
Because a pair has just 2 elements. 123 has three elements.
Just watched this video, is it not nc1 + nc2 ?
for 4, 4c1 + 4c2 = 10
haha i made the mistake of making permutation.......
Koi nh beta. Glad you got your mistake, try to improve and remember it for the future.
@@Pepcoding thnx sir and plz make more video regarding trees and graph also.
In this question, the equation is f(n)=f(n-1) + f(n-2)*(n-1) and not f(n)=f(n-1) +(n-1)* f(n-2). There is a difference between the two. In the former , recursion will take place first .