Pascal Triangle | Finding nCr in minimal time
Vložit
- čas přidán 4. 04. 2023
- Problem Link: bit.ly/3jY4iuF
Notes/C++/Java/Python codes: takeuforward.org/data-structu...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
00:51 What do you mean by Pascal's Triangle?
02:27 3 Types of problems that might be asked to you
03:52 1st Type Problem Statement
06:56 Formula shortcut
07:49 Code
09:46 Complexity
10:31 recap
10:54 2nd Type Problem Statement
11:38 Brute force
12:18 Complexity
12:37 Optimal solution & Deep dive into formula and observation
15:11 Minor changes and formula
17:27 Pseudocode
19:06 Complexity
19:21 3rd Type Problem Statement
20:00 Brute force
20:07 Pseudocode
21:17 Complexity
21:50 Optimal Solution
22:19 Code
25:16 Interview Tip : Code Quality
Please watch our new video on the same topic: czcams.com/video/bR7mQgwQ_o8/video.html
Recursion without a base case 😁😁
Please do like the video, it won't cost you anything, but it will highly motivate me :)
Did this problem move to easy from hard?
Ofcourse we do......
But not only for motivation,but also for your efforts.......😊
Such type of free content is very helpful for those persons who are not capable to buy an expensive course......👍✨
done bhaiya
your videos actually got me out of depression and gave me aa hope at becoming better at DSA!!!!
got better?
What's the status now champ?
#include
using namespace std;
class PascalsTriangle{
private:
int Ncr(int n,int r)
{
int ans=1;
for(int i=1;i
We can reduce the time complexity to (n^2/2) by running the inner loop only for row/2 times and assigning values symmetrically because the pascals triangle is symmetric.
Thank you for the videos!
that's what I was thinking
To add symmetry to the result, you need to run a loop right? Or is there any other ways?
I always amazed the level of intelligence you have brother, Thank you for this playlist, Trust me your playlist is making thousands/millions of students better coder.
Understood! Super awesome explanation as always, thank you very very much for your effort!!
nCr = nC(n-r) so, we can take i < min(n, n - r) it is more efficient
will not affect complexity though so no need
Loved it, very well explained!
used to solve this problem by myself but the solution was brute force method. Never have I ever thought this problem can be solved by such observation. Hats off to the effort Striver puts in his video. Incredible!
Finally I was able to solve a problem before looking at your solution. That too hard one 😎 All thanks to your foundational videos on Arrays ♥
Watched the video anyways. Just to look at your approach
Thank you very much for this amazing course 🎉❤
🔥🔥 love your teaching 🤗 you are my inspiration
very very easy solutoion ..every time i can think about only brute solution but u gived both the solution at same time which is fantastic ...amazing love the way you teach
Awesome explanation as usual💗
Amazing explanation. thanks a ton. Working harder to make u proud.
APPROACH TO THIS PROBLEM IS SUPER SE V BHT BHT BHT ZYADA UPAR🔥🔥🔥🔥🔥🔥🔥🔥🔥
Your explanation is superb ❤️❤️..
Ride on Striver.
Thanks for taking us forward,, Striver❤
Awesome video. Thankyou striver ❤❤
Frankly speaking I am not able to understand Pascal triangle problem until I watched this video, Earlier I see almost 5-7 videos on CZcams , from those videos I Get what is the pascal triangle, but didn't able to solve the problem. After watching this video, I have confidence to solve any problem based on pascal triangle.
verrry good explanation and even the methods of solving the given problem😇
You are the best !
understood, thank you!
It's a very tricky problem based of math nCr.. approach by you is really good
Understood brother, Thanks for this amazing amazing explanation...
Great work....
Excellent 👌
Understood, thank you.
Keep doing great 👍🎉
understood :) thankyou striver
Understood very well
Excellent👍👏
understood. Respect!
Understood, thanks :)
superb explanation
good video ... understood
understood ..Thanks🙂
Understood✅🔥🔥
understood!!
You are the GOD of dsa
Thanks bro. Understood
Thanks a lot my ninja.....
Understood❤️
450 questions will need many months of continuous hard work. Hats off bhaiya
We have already covered > 60%, trees : 56, graphs: 56 dp: 56 ;)
there is no good playlist for string on CZcams only one or two videos and its and important topic please start with string@@takeUforward
Each row is binomial expansion coefficient for certain power. We can directly use combination formula to get it .
whats the intiution behind (n-1)C(r-1) ? can someone plz tell
I am also looking for its intuition, thanks for raising this , but nobody has still answered on it yet
12:43 yaha se dekh Bhai agr phir bhi na smjh aye TB btayio
Understood!
understood 😇
understood !
Understood ❤
Understood 🎉
Love it
Striver!!Please upload videos on binary search.
helpful❤
Understood! sir
I don't get the point where he bring the formula. How did he arrive that formula will give the output? anyone knows the answer?
This is great...I hope you earn enough from all this 😊
@striver bhaiya could u please make a video on what are sample input output test cases constraints and how to code on online compilers on coding platforms as i am beginner and i am facing difficulty in understanding these
you sorcerer :)
Python code for 1st variant
def pascal(n,r):
res = 1
for i in range(r):
res = res * (n-i)
res = res/(i+1)
print(res)
n = int(input("Value of N"))
r = int(input("Value of R"))
pascal(n-1,r-1)
understood 👌👌👌👌❤❤❤❤
Understood
3:40 4th type question can be asked is sum of nth row
ans :simple left lift 1 by (n-1) that is 1
Awesome
understood bro
understood :)
Thanks Striver, my code is not passing because of spacing issue in between digits😌 we can do in more way, pascle is nothing but power of 11, so if it's asking for N, then just run a loop from 1 to N and calculate the power(11, i), push into the vector if spacing is not considered. Stuck with spacing.
Hi, Did anyone here faced probelm in Test Case 50 of Gfg. If yes, then can you please expalin how did you tackle?
understood
SDE Sheet: Day 1 Problem 2 Done!
so how many have you done till now>?
we can use recursion right ??
generate the answer for N-1 and the add another row by with the help of last row of generated answer and add this row and return the final answer
Understood.
We personally call it Parallel computing or Stacking method.
Hey striver, I was having a doubt that will you cover up some competitive programming concepts in this course or not?? Because covering all cp topics will make this course legendary and no one will be able to surpass this level in generations.
😂😂😂lol
class Solution(object):
def pascal(self, numRows):
pt=[[1]]*(numRows)
pt[0]=[1]
for i in range(1,numRows):
pt[i]=[1]*(i+1)
for j in range(1,i):
pt[i][j] = pt[i-1][j-1]+pt[i-1][j]
return pt
for generating entire pascal's triangle.
Or you could use the previously stored values to generate the lower rows which will take O(n*n) TC
please do reply bhaiya,in your sde sheet you have not given explaination of heaps part :(,please cover this urgent solution of heapss problems in your sde sheet
Need some advice! I have been doing DSA consistently for the last 1 month but I wasn’t able to come up with an efficient solution for this problem by myself. I don’t know if I am doing something wrong. Is this actually kind of advanced or I just need more practice?
Can you pls pls plsssss do strings before binary search next plsss🙏 ?
Understood..........
Understood❤❤❤❤❤
can we do it with that apprach as we have seen them as the square , cube and quadraple of 11 as 11,121,1331....and so on so we first convert that no . to string and then string to that vector and then print:)
this will take as overall complexity of O(N) in worst case
Can someone please explain how you intuitively figure out that a formula like the binomial coefficient needs to be used in a problem like this? I can't see how it would occur to me unless I've memorized it.
I think to print n rows for pascal triangle would fail for large test cases even if we take MOD of 1e9 + 7
We can use ncr=nc(n-r) when r>n/2 10:44
can anyone give me the java solution because we implement similar logic in java they are showing me the:- n compatible types: List> cannot be converted to int[][]
int [][]ans = Solution.pascalTriangle(n); so plz help me
Thanks
Bhaiya, Combination wale question ki bhi list bana do please, Ya phir Combination ke concept ke baare mai ek acchi video bana do.
🔥🔥
00:04 Pascal's Triangle - A pattern of numbers where each number is the sum of the two directly above it.
02:05 Finding element at a specific row and column in Pascal Triangle.
06:48 Shortcut for finding nCr in minimal time: multiply numbers from n to n-r+1.
09:11 The numerator in nCr calculation keeps getting multiplied and then divided with the value of i+1.
13:39 Pascal Triangle formula is used to find nCr in minimal time.
15:59 Pascal Triangle for finding nCr
20:22 Generate Pascal Triangle row in minimal time
22:16 Optimal solution for finding nCr in minimal time
26:16 The CZcamsr encourages viewers to subscribe and engage with their content.
10 rs ki pepsi striver bhai ki explaination sexyyy!!!
Which whiteboard app striver is using for explaining ?
Goodnotes
Bhaiya gfg mein yeh 2nd method 50th test case mein error de raha hain ,long long bhi use kiya fir bhi nahi chal raha
Waiting for string series
striver ❤
can't we do like caclulate numerator (10*9*8) and denominator(3*2*1) and then divide. 720/6 = 120
Understood
instead, for the first problem, the loop should run for min(r, n-r) and not 'r' because if it is 10C7, r is bigger than n-r
I tried solving ncr problem with this approach but still test cases are failing for ex 69c43
You can search ncr problem gfg ... Can you try solving with first approach along with min(n-r, r) modification and let me know?
respect++