Catalan Numbers Application | C++ Placement Course | Lecture 28.6
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- Complete C++ Placement Course (Data Structures+Algorithm) : • C++ Full Course | C++...
Telegram: t.me/apnikaksh...
Instagram: / dhattarwalaman
Notes of this Lecture:
If someone has difficulty in understanding the code then follow these steps :
1. dry run on paper with start =1 and end =1
2. dry run on paper with start=1 and end =2
Now finally,
3. dry run on paper with start =1 and end =3
You will definitely understand the concept and code after these 3 steps.
We MUST use DP or Memoization in such kind of problems.
1) DP approach for catalan Numbers :-
int catalan(int n){
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i=2;idata += s;
inOrderChange(root->right,s);
}
Node* copyNode(Node* root,int s){
if(!root)return NULL;
Node* n = new Node(root->data+s);
n->left = copyNode(root->left,s);
n->right = copyNode(root->right,s);
return n;
}
vector possibleBST(int N,unordered_map &memo){
if(memo.find(N)!=memo.end()){
return memo[N];
}
vector bsts;
for(int i=0;ileft = j?copyNode(j,0):NULL;
n->right = k?copyNode(k,(i+1)):NULL;
bsts.push_back(n);
}
}
}
memo[N] = bsts;
return memo[N];
}
vector allPossibleBST(int start,int end){
unordered_map memo;
vector v;
v.push_back(NULL);
memo[0] = v;
vector vv;
vv.push_back(new Node(0));
memo[1] = vv;
vector bsts = possibleBST(end-start+1,memo);
for(auto i:bsts){
inOrderChange(i,start);
}
return bsts;
}
Note That We cant use 2D array as memo because memo[0][2] or memo[5][7] have same BST with just different numbers, besides no overlapping is occurred for any start and end numbers, only their differences are overlapped. So we will use 1D array / map for memo and change BSTs numbers with inOrderChange() function.
Happy Learning ...... :)
thks for sharing this
thanks
at 13:48 2nd one is not a BST
*Correction at 13:36 - the 2ndTree is not a valid BST and the correct version of this will be simply :
1
\
3
/
2
just came to the comments to see someone clarify this thing only 😂
@@schrodingerscat6189 +1
thanks bro
Respect +1
i was thinking that too!
Sir your videos are a real help sir you are doing a great job.
Lots of love and blessing for what you are doing.Cant wait for your job
Sir nhi ma'am.....😂
Both Aman bhaiya and Ma'am.
the formula of catalan numbers is wrong, it should be Cn+1 = Σ(CiCn-1) or Cn = Σ(CiCn-i-1)
pin this comment
Yes that's why I was not getting c2 value correct .
Cn+1= sigma CiCn-i hona chaheye shayad 1 ki jagah i hoga bro
this code is very complex to understand.
true, I am skipping this
One line python code to generate Catalan numbers,
catalan = lambda n: 1 if n==0 or n==1 else sum(catalan(n-1-i)*catalan(i) for i in range(n))
*Much love and Respect to whole Apna College team for providing this content on TH-cam.* ♥️
Keep Hustling 🔥
Thank you so much Aman bhaiya and team!!
my code for the catalan sequence looks like this and is better in some way as the values are not getting calculated individually every time
but using that same values we already calculated in previous iteration
space complexity increased in my code :
int catalanUtil(int arr[], int i, int n) {
if(i < 0) {
return 0;
}
int ans = arr[i]* arr[n] ;
n++;
i--;
ans += catalanUtil(arr, i, n);
return ans;
}
void catalanNum(int n) {
int c0 = 1;
int c1 = 1;
int arr[n];
arr[0] = 1;
arr[1] = 1;
for( int i=2; i
hello to people waiting
13:53 possible BSTs 2nd BST is wrong
Koi last code ko samjha do pls
bhai kaafi logo ko samajh nhi aaya last wala, mujhe bhi nahi aaya
Thank you 🙏🙏
if u r seeing this for the first time, then rewatch this, u probably won't get this fully in 1st watch
Did u understand in second watch?
@@jiosim1377 Nice Question!!
Very good explanation di👍👍✨✨
**The formulae of Catalan number was incorrect.Cn-i-1 should be there instead of Cn-i.
The formula of Catalan Number is (Ci-1)*1*(Cn-i) when i goes from 1 to n.
and
The formula of Catalan Number when i goes from 0 to n-1 as in this video is (Ci)*1*(Cn-i-1).
How many times are you going to repeat preorder ? It's okay to copy paste.
Video ki length jitni jada ho utne jada pese milte h neha didi ko
1:40
4:10
8:42
9:09
13:40
15:30
16:20
21:20
23:00
24:00
24:20
25:00
Kehna kya chahte ho😂
Thank You Apna College For This Amazing Lecture :)
constructTrees was complicated. I don't understand the explanation 😥
Students k liy Aman Dhattarwal se best koi nhi 😍
I think the recursive sequence for Catalan number is wrong at 1:32
What is the correct one then?
At 16:05 why the possible BST are two only, 3 can be connected in the term 1 in more 2 possible ways......
Very nice 👍👍
Bhaiya notes kab milege
N=3 then only 4 BST Tree make
Mam please upload notes
anyone continue this series please comment ...
yes, what do you want?
@@adityabhandari6688 bro are you able to understand the last code if yes can u explain?
@@jiosim1377 no, i didn't understand last program so I skipped it. Also it is better to use dynamic programming in such questions which we will study at a later stage
@@adityabhandari6688 bro btw how has your progress been so far with this course? R u practicing questions side by side or only doing the questions from this course?
@@adityabhandari6688 bhai mujah bhi samaj nahi aaya :( ........mere kuch oor print ho raha ha
Notes Please
Sir mene B.A programme kar rakhi h but mujhe web development me interest h kya mujhe bhi amazon jesi company me job mil sakti h. Plzz video on this topic bahot saare students h jo non technical se but une web creation or web development aati h or usi me career banana chahte plzz sir es par jarur video banao
the second figure is wrong in 13:54 how can be 3 left child of 2
Why am i not able to understand the logic of the last code written? Is it only me?
me too
please make python lectures too...
I think this video suppose to be possible binary trees, not BST
Pls somebody help me My VS-code is not running in the terminal it's showing that final link failed:No space left on device .
there are many errors and problems to be faced in VS-code , i would suggest u to use GDB online compiler
space compkexity zayada hoga(memory leak hona ka karan) ya harddisk tumhara full hogaya ha
oye i am ritwik ran hope i get placed to product based scene
Formula to calculate the next Catalan Number is wrong #correction at 1:15.
What is the correct one then?
*999k*
C2 or C3 upper jo mathematical definition btai h usse satisfy nhi kr rha...kya h ye
very difficult to understand
I tried to optimise this method
now loops runs from 0 to (n/2) [so i think].
and it is giving right ans too.
can someone tell me is optimized or not?
int catalan(int n){
if(n
It is not optimised it's the same
code ka dry run to karado
what is the name of the instructor?
Shraddha Didi
Ia this course good or does the content become worser as we proceed??
yeah it is good, but you have to practice questions sideways as well
Guyzzz how willl we get the notes ...🙄
pehle khud samjhiye uske baad dusre ko samjhaiye...(BST)
Dtcj
Worst Explanation, after watching this i am more confused now :)
After 19:00 khucch samaj nahi aaya :(
In 2nd example at 13:45 shouldn't it be
1
\
3
/
2
?
vector to dhang se padha do
pehle khud samjhiye uske baad dusre ko samjhaiye...(BST)