K-th Symbol in Grammar | Recursion | Recurrence Relation Explained | GOOGLE | Leetcode - 779
Vložit
- čas přidán 23. 10. 2023
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 1st Video on our Recursion Playlist.
iPadPDF Notes - github.com/MAZHARMIK/Intervie...
In this video we will try to solve a strange Recursion Problem - K-th Symbol in Grammar (Leetcode-779).
There are other ways to solve this problem, if you guys want more solution videos on this problem, kindly let me know through comment.
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : K-th Symbol in Grammar
Company Tags : GOOGLE
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/k-th-sy...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook
i guess recursion is the hardest and the easiest topic simultaneoulsy...jb smjh aata h to kya hi smjh aata ha..aur jb ni aata to poora upar se jata h ....thanks bhaiya
😇🙏 so true
@@codestorywithMIK
sir please upsolve contest of leetcode && start a series of competitive programming
I can do medium leetcode but can't do a single in codeforces
True
bhai dil ki baat kah di.
Very good teaching with details 😮😊😊😊😊😊😊
Nobody explains so smoothly like you. When I come to your channel for solution after trying all the ways, I just expect a solution of an EASY question, no matter what is the level of the question on leetcode.😄
Means a lot to me. Thank you so much 😇🙏❤️
Bro you explained it very well even I watched Aditya verma but didnt understand then I watched yours.Now I completely understood. Thanks bro
Muje yahi solution samaj ata he!! Thank you so much for explaining this very well!
Nice❤❤❤
My mind after seeing explanation " bhai aapka knowledge to kaamal ka hai" .
your explanation just blows my mind.
Best ❤❤❤❤
Thank you so much for this legit explanation. You are just out of the world
sir please upsolve contest of leetcode && start a series of competitive programming
I can do medium leetcode but can't do a single in codeforces
I am planning soon to start contest videos. Just trying to squeeze time from office and travel plans. Will soon begin.
Thank you so much for watching 😇🙏
Great video 💯
Legit explanation man. You are a 💎
Thanku bhaiya ❤
Mind blowing explanation 😊
Thank you so much 😀
Legit explanation 👌🏻
What a fantastic explanation 🙌🙌
you are a magician. loved the explanation.
Great Explaination....
Thank you 🙏😇
best video ever. thank you.
Thank you 😇🙏
Thank You for helping me out mik bhaiya.
Most welcome 😇🙏
Thank you for the amazing explanation 🥰❤
You’re welcome 😊
Brute force hua , Sir I relate problem with bucket water jo abhi past me aya tha also find repeat case etc but unfortunately stuck from last 2 hours thx for today problem 😊😊
Done ✅
i was trying to solve it using recursion similar to count and say problem..but this qn was completely different i liked the idea behind this question. Thank you bhaiya understood!
Thank you for watching 😇🙏
Hey there!
Your video explanations are damn amazing !!
I request you to also start making the solutions of the weekly and biweekly leetcode contest solution.
It will help a lot.
I am planning soon to start contest videos. Just trying to squeeze time from office and travel plans. Will soon begin.
Thank you so much for watching 😇🙏
I'm solving recursion,dp problems bcoz of ur depth explanation.
Please provide weekly contest solutions too, it would be greatful .
Thank u
I am planning soon to start contest videos. Just trying to squeeze time from office and travel plans. Will soon begin.
Thank you so much for watching 😇🙏
amazing how one find such patterns
Yo🎉
u got a subscriber🤗
Thank you and welcome to my channel 😇🙏❤️
Didnot understand the part why one half would be the same and the next half would be the complement. If possible, can you make a video using bit manipulation technique.
I was able to do brute force, also tried to solve using recursion after reading that the current solution was dependent on previous one, but unable to write the recursive function parameter for 'n' and 'k.
Loved your solution ❣
Thank you for watching 😇🙏
can you share brute force here???
@@harshtiwari416
this is the brute force: but not accepted give TLE->
class Solution {
public:
int kthGrammar(int n, int k) {
vectorarr(n,vector());
arr[0].push_back('0');
for (int i = 1; i < n; i++){
for (int j = 0; j < arr[i-1].size(); j++){
if (arr[i-1][j] == '0'){
arr[i].push_back('0');
arr[i].push_back('1');
}
else{
arr[i].push_back('1');
arr[i].push_back('0');
}
}
}
return arr[n-1][k-1] - '0';
}
};
you can see it in discuss section of leetcode@@harshtiwari416
bhaiya i am facing problem in converting the memorization code into tabulation so to understand properly to convert it into tabulation which video of your dp playlist should i watch?
btw understood today recursion intuition :)
bhaiya i want your suggestion i am not understanding dev topics (backend) and also not able to solve new problems and along this i have to manage college studies feeling overwhelmed in this situation what should i do any suggestion
I came up with same observations, but could not think of recursion instead directly did with loop
Please upsolve contests also it would be helpful
I am planning soon to start contest videos. Just trying to squeeze time from office and travel plans. Will soon begin.
Thank you so much for watching 😇🙏
@@codestorywithMIK Thanks for yr effort
did on my own this was kinda similar to 799. Champagne Tower :p
not the logic but the intuition yes :)
i would encourage people to solve that too after this question.
My solution is a bit different
class Solution {
public:
int solve(int n,int k){
if(n == 0){
return 0;
}
int prevChar = solve(n-1,k/2);
if(prevChar == 0){
if(k%2 == 0){
return 0;
}
else{
return 1;
}
}
if(prevChar == 1){
if(k%2 == 0){
return 1;
}
else{
return 0;
}
}
return -1;
}
int kthGrammar(int n, int k) {
return solve(n,k-1);
}
};
Thanks a lot 😇🙏
@@codestorywithMIK sir please upsolve contest of leetcode && start a series of competitive P
I can do medium leetcode but can't do a single in codeforces
how did u approach and should we start with some dry run on copy first
Yes always do some copy work first. It helps to figure out and understand qn
Bhaiya hmko ye thora thora campaign tower jaisa lag rha hai .... Kya hm sahi soch rhe hai, kyuki abhi hm ye question try nhi kiye hai
Yes pretty much same.
bhaiya contest solutions ki videos bhi upload kr diya kro please
I am planning soon to start contest videos. Just trying to squeeze time from office and travel plans. Will soon begin.
Thank you so much for watching 😇🙏
another solution :
int kthGrammar(int n, int k) {
if(n==1 || k==1) return 0;
int prev= kthGrammar(n-1,(k+1)/2);
if(prev==1) return k%2?1:0;
return k%2?0:1;
}
public class kthGrammar (int n,int k){
if(n==1) return 0;
if(k%2==i)
return kthGrammar (n-1,(k+1)/2)==0?0:1;
return (n-1,k/2)==0?1:0;
bits
int count =Integer.bitCount(k-1)
return count %2==0?0:1;
Three Lines of code :
int kthGrammar(int n, int k) {
if(n == 1 && k == 1) return 0;
int ans = kthGrammar(n - 1, (k + 1) / 2);
return (k % 2 == 0)? !ans : ans;
}
class Solution {
public:
int f(int n, int k ){
if(n == 1){
return 0;
}
int temp = f(n-1,(k+1) / 2);
if(temp == 1){
if(k%2 == 0){
return 0;
}
return 1;
}
else{
if(k%2 == 0){
return 1;
}
return 0;
}
}
int kthGrammar(int n, int k) {
return f(n,k);
}
};
bro please provide notes
Sure thing. I have added the PDF link in the Description. YOu can click this below as well
iPadPDF Notes - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-779-K-th%20Symbol%20in%20Grammar.pdf
Thank you
No sound
Please refresh. It will come
should i solve leetcode daily with college exams
Hi there,
First get prepared well for exams. If you get time , then only solve leetcode.
Else, you can continue leetcode post exams. Because good grades are helpful in many companies hiring.
I maintained the consistency of 3 months
I had observed the pattern but unable to write recurrence 🥲🥲
that is true , we can observe the pattern but unable to write recurrence relation. @codestorywithMIK sir can you please why this happens? please reply sir !!!!!!!!!!!!!!!!!
Hey,
Actually this happens in some of the problems to me also. So in my case, i usually do a dry run of 2-3 test cases to figure out if the code works. Or what is missing.
Doing a dry run is also expected in interviews. When you write a code, you must double check with 1-2 examples dry run. It will give you extra points as well in interviews.