Kth Symbol in Grammar

[@amansinghal4663]

Before watching this video: I wasted first 30 minutes trying to solve it using loop =>RESULT - Got TLE I wasted next 15 minutes trying to solve it using IBH method learned in previous videos =>RESULT - Got TLE again in the same test case, but i was proud of myself that i was able to code it using IBH method so easily. Then i watched this video till 9:32 and then paused and then kept trying for next 45 minutes trying to observe any pattern and code it using IBH. =>RESULT - Accepted The level of understanding this man has given me in recursion is just exceptional. Thanks to one of my college senior bhaiya who recommended me this channel. He just told me that there is no other youtube channel that has taught recursion so much easily as taught by aditya verma. The only thing missing from your videos is time complexity and space complexity of your code. It's very difficult for me to find time complexity of recursive solutions.

[@svastiishrivastava9291]

Have you find any video for time and space complexity

[@LightYagami-ib6fb]

I like your style of asking people to stop and think in vital positions, helping them to think more deeply and not just mug learn something. Thank you for the efforts!

[@prativadas4794]

you are a blessing for many people like me. thank you for explaining everything in such a smooth way.

[@mriit3025]

bro! it's simple and to the point explaination, first because of length i was going to leave, but the line you mentioned " Your observation is tested" ignited me to continue!..

[@akashrajput3731]

Thanks aditya for providing us such a great content on Recursion

[@yuktikumari6042]

I wonder how did you study these topics so nicely ?

[@ananysharma9290]

Yess Sir these are Amazing but we Seriously need graphs

[@rick.exe1]

Bro how did you even come up with this solution.Mad respect only !.

[@AP-bk8vq]

Great stuff! I'm following this series daily...Please try to upload GRAPHS next..there isn't much good content on Graphs on the internet and your videos would surely help us!

[@abhaygupta8754]

please make graphs simple for us. i know you can do that

[@yasharora6818]

Follow striver's graph series, it is brilliant.

[@ajinkyakale4391]

Le Striver: Let me introduce myself

[@shreya-tf5go]

I solved this solution on my own and i was so happy .It happened all because of your teaching .Thanks bhaiya Hats off.

[@Liftsandeats]

At 8th minute mark, I paused the video took me 30 minutes to code up a solution involving only recursion and a couple of if statements in Python. The previous videos build up this confidence in me to solve it before watching the video itself. Now I am gonna watch the video and see your approach as well!!

[@thinkingmad1685]

Did you code in paper or ide?

[@Liftsandeats]

@@thinkingmad1685 paper for logic building and then write the code in vscode

[@waka91]

@@Liftsandeats can you share your soultion if it is different than aditya's?

[@DroidHolicOfficial]

What an interesting problem. All about observation as you said! You explained the problem so well and also the observations, that the solution became so damn simple! When you explained the problem statement, i did notice that first half of next row was same as previous but didn't notice that second half is just complement of previous row. RECURSION IS LIKE MAGIC INDEED!! const kthGrammar = function(n, k) { //Base Condition if(n == 1 && k == 1){ return 0; } //Find the mid of length of the nth row let mid = Math.pow(2, n - 2); if(k

[@the_humble_lazy]

thanks internet for making us meet with aditya's content where we watch for out betterment and thanks us also....recursion and dp god he is for sure

[@VishalSharma-hq5ti]

In base condition, we can have if(N == 1 || K == 1) since, K == 1 for any N, ans will be 0 only so it might save a few function calls also in this case.

[@nrbtreasure6240]

Great!

[@DroidHolicOfficial]

Or we can just ignore this K == 1 condition and just say if (N == 1) return 0;

[@harishsn4866]

This is by far the best explanation I found for this problem. Thanks.

[@himanshuarora539]

When you said this question is only to test our observation skills, i gave this one more try and was able to solve on my own. Thanks

[@saitrinathdubba]

Great Stuff !! Thank you !! People here is the alternative python solution, this relies on the if k is even then we will compliment the output other wise we continue, every time we reduce the value of k by half depending on if k is even or odd. Once again thank you for the great content !! class Solution: def kthGrammar(self, n: int, k: int) -> int: output = self.sub_kthgrammar(n, k) if output: return 1 return 0 def sub_kthgrammar(self, n:int, k: int): if n == 1 and k == 1: return 0 if k%2 == 0: # if k is even return not self.sub_kthgrammar(n-1, k/2) else: # if k is not even return self.sub_kthgrammar(n-1, (k+1)/2)

[@mihirsharma2338]

Or we can just typecast the return value with int()... Here's my code with little bit of change.... //// def kthGrammar(self, n: int, k: int) -> int: if(n==1 and k==1): return int(0) mid = (2**(n-1))//2 if(k

[@ankittjindal]

if(n==0 || n==1) return 0; int mid = pow(2,n-1)/2; if(k

[@himanshidixit6406]

honestly sir you're a great teacher and your explanations are wow..never stop uploading these videos..they are very helpful..

[@gauravraj2604]

Hey @Aditya Verma, thanks a lot for this awesome collections of yours. Your every video is not just a video of any problem, it teaches us so many concepts in many ways that help us later when we revisit such topics again. You are a true gem.

[@paragroy5359]

Thanks for the playlist sir.....your channel is extremely helpful for the placement preparation

[@kapilchoudhary2922]

East or west Aditya boss is the best!!

[@TheAdityaVerma]

❤️✌️

[@amayatre3558]

baapre kitna jyada easy bana diya question ko , hats off to you sir

[@BECSAQUIB]

Great thanks from the core of my heart ❤️

[@sanchitagarwal9651]

today i got the real essence of recursion. ...thanks bhai a lot!!!!!!!

[@SDE_FACT]

I have no words for your explanation. Bass itna kahunga ... Aap ho to DSA me aag laga denge bhaiya❤️🥺

[@namekuldeep]

very good .. Other way also mentioned below ...apart of recursion ... if (N == 1) return 0; if (K

[@nikitajaiswal9112]

Amazing 😍thank you so much for providing great content free of cost

[@rajatgupta-ld1wg]

I did this question around 15 days before watching your video but wasn't clear about the basics.. Now it seems i can do this question anytime as you have cleared the basic concept. Thanks bro!. You are awesum as always.. :D

[@studyacc1234]

if I got a penny every time Aditya said the word 'cool', I would have been a billionaire by now. hehe jokes aside - you are a bomb teacher!

[@codertan4109]

So wonderful explanation!!! Thank You so much for this Bhaiya!!!

[@tusharagarwal3475]

Bhai dil se bhot bhot dhanyavaad kya explanation thi bro.

[@AngadSingh97]

Kya sikha rahe ho bhai, thank you so much.

[@tsupreetsingh]

Bhai Graphs par bhi bano do ek playlist , bohot help hoga !! 🙏🙏

[@sayalikulkarni4717]

It will be better if you mention the time complexity of every problem along with the solution. Thanks!!

[@Vickerdeer]

o(n) complexity for Time & space

[@radium990]

++

[@suraj_cricclub3630]

Aditya sir your are legends ❤️

[@044_karan9]

Best playlist for recursion👍

[@fenilbhavsar7892]

God bless you brother. You are a pure soul.

[@Lucifer_movies]

Nice and crisp explanation

[@Anonymous-gl7gs]

best explanation

[@svworld01]

Amazing explanation 💕🙏

[@paritoshdadhich2954]

Thank you for such a clear and simple solution

[@neharikakhera6411]

Thanks for such a great explanation.

[@bharanidharan.m4245]

how to find the method for a problem that uses IBH method or ip-op method .

[@pratheeksha616]

Great content, A playlist on GRAPHS please

[@riteshgangwar7192]

Awesome sir, best playlist for recursion on KZbin,,plz plz , make playlists on trees

[@sejalzambare1896]

you made it very easy! Thankyou! great work!

[@vedantgolash6084]

waah yr ..maja agya aditya bhaiya

[@AmanKumar-qz4jz]

congratz sir for 2 lakh subscriber

[@anmolsingh9084]

Sir how to compliment the function in solve(n-1, k-mid) as m not able to do so. Basically asking how to NOT the 2nd half compared to the n-1 1st half.

[@ujjwal824]

Simply use this: if(kthGrammar(N-1,K-mid)==0) return 1; else return 0;

[@DragoonBlod]

Take the xor of the return value with 1

[@rounakbajaj1273]

@@ujjwal824 thanx bro..

[@pawanlok1776]

** Thank you , Observation is quite important to solve this question

[@mutyaluamballa]

man this is so cool, the moment you asked me to pause and asked us to observe. I got a different answer. int kthGrammar(int n, int k) { if(n==1) return 0; int k_ = ceil(k/2.0); // its the previous index of current k, when n-1 int prev = kthGrammar(n-1, k_); if(k_ == k/2) return !prev; return prev; }

[@endlesslearning26]

Bro same here But I just complicated it a bit intially Induction step:- Val=find(n-1,ceil(k/2)) If ((Val+k)%2==0){return 1} Else{return 0}

[@thinkingmad1685]

Can u elaborate what you did

[@shreya-tf5go]

can anyone please suggest good resources to learn 2 pointers?

[@bambu-mq9zg]

my approach def kthGrammar(self, n: int, k: int) -> int: def rajeev(n,k): if n==1: return 0^((k+1)%2) return ((k+1)%2)^rajeev(n-1,(k+1)//2) return rajeev(n,k)

[@SadhanaSharma]

explicit explanation .. Thankyou sir!

[@037_abhinavkumar3]

What's the induction condition in this question?

[@rohitnandagawali1589]

int kthGrammar(int n, int k) { if(n==1 and k==1) return 0; //this is given in question int mid=pow(2,n-1)/2; //pow(2,n-1) gives length and '/2' helps to find mid if(k

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@souravkumardas8905]

best explanation ever.

[@shibanidas7018]

Bro I could solve this before watching the video by following your series, Not only u solve these problems but teach us HOW TO THINK U r god !!!!

[@abbas.muzammil23]

Time complexity: O(n) right?

[@RonitSagar]

Can anyone tell me ....which value is returned to the calling function in recursion. base condition or other part(hypothesis/induction)

[@MalobikaNandy]

really good video.. thanks a lot

[@Akash99D]

What's the induction step here? could anyone point out.

[@nidhigalmale112]

Python Solution: class Solution: def kthGrammar(self, n: int, k: int) -> int: if k==1 and n==1: return 0 mid = 2**(n-1)/2 if kmid: return (self.kthGrammar(n-1,k-mid)^1)

[@karanbisht6359]

thnks ..... i got little confused on complement part !!!

[@piyushmishra889]

sahi ho bhai tum, naam suna tha , dekha to acha laga

[@shikharjoshi2998]

btw what was the induction step in this code?

[@maniish-sgh]

Great work buddy🥂

[@arjunankathattichandrashek1997]

very beautifully explained!!

[@akankshasaini3779]

please end me time complexity bhi btaya kro, recursive functions me dikkt hoti hai

[@kailashjangir1530]

bhaishab magic tha ye to bilkul magic

[@asishcodes]

Can someone please tell me which part of the code is hypothesis and induction

[@ElectronToInterface]

def kthGrammar(n: int, k: int) -> int: if n == 1 and k == 1: return 0 mid = (2 ** (n-1)) // 2 if k

[@cse077mukulrana]

We can also done this using XOR of string and add to the end And after building find k element simple Time complexity would be O(max(N, K)) Space complexity would be O(N) And the second method is what you told here I guess

[@rohitjoshi6335]

This question was great!

[@satyamagarwal0302]

what will be the time complexity of this code?

[@SalmanKhan-vu4bk]

Please upload video on graph 💓💓

[@adityapandey5264]

Excellent explanation.

[@neo9530]

I understood how it is working but I am not getting why it is working? If I take an example say(3,3) and back trace it from the base condition to first function call. It is giving me right ans bhut why it is giving correct ans? That i am not getting. Plz can someone explain.

[@aspiring_Sr.dev_Om]

we can also find mid by :-> mid = pow(2,N-2); , jst simple maths

[@shubhamjha5738]

can anyone explain time complexity of above soln.

[@biswajitsahoo1456]

how can u compliment by just putting a ! sign in code plz can u explain it or share a link that will help me

[@faheemuddinnaseem397]

perfectly explained i love it

[@subhajitdutta5216]

Can't we use DP in this problem?

[@ashutoshshukla5398]

The time and space both would be O(N) for this. Right?

[@pinkkitty6553]

The java bitwise not operator (~) might fuck up your code logic, as it also changes the most significant bit which denotes the sign of the number Use ternary operator instead Return (solve (n-1,k-mid)) == 0 ? 1: 0:

[@atharvsakhala9469]

Can you prove by induction that the relationship you found actually holds between next rows?

[@bijendersingh8141]

int kthSymbol(int n, int k) { if (n == 0 || k == 0) { return 0; } int symbol = kthSymbol(n - 1, k / 2); return ((k / 2) * 2 == k) ? symbol : !symbol; } call => kSymbol(n-1, k-1) works for larger inputs.

[@bijendersingh8141]

final return statement can be changed to return (k&1) ? !symbol : symbol;

[@vedantshinde3717]

What change should be done in the code to print this grammar instead of getting a single bit ?

[@AnuragSingh-jq6jn]

I wonder how did you study these things so well on your own because during your Btech youtube barely had any resources.

[@yashshimpi3093]

k/2 bhi use kar sakte hai na 🤔🤔

[@sandipan_c]

def solve(n,k): if n==1 and k==1: return 0 else: if k%2==0: return 1-(solve(n-1,k//2)) else: return solve(n-1,(k+1)//2) print(solve(4,8)) this is a different approach.

[@angadrajsingh4311]

Amazing brother!!!

[@susmitjaiswal136]

faster than 100% submissions...aditya verma i loved your series int kthGrammar(int n, int k) { if(n==1||k==1) return 0; else{ int a=kthGrammar(n-1,(k+1)/2); if((k+1)%2==0) return a; else return 1-a; } }

[@sohamnandi7526]

can you please explain this solution.

[@chandanbharti5207]

@@sohamnandi7526 The given code implements a recursive function called `kthGrammar` that returns the value at position `k` in the `n`th row of a grammar sequence. The grammar sequence is defined as follows: - The first row is always "0". - For each subsequent row, each element is created by taking the element at the corresponding position in the previous row and replacing it with two elements based on the following rules: - "0" is replaced by "01". - "1" is replaced by "10". The function uses recursion to calculate the value at position `k` in the `n`th row by dividing the problem into smaller subproblems. Here's a breakdown of how the function works: 1. Base Case: If `n` is 1 or `k` is 1, it means we are at the first row or the first position in any row, so the value is always 0. Hence, the function returns 0. 2. Recursive Case: a. The function recursively calls itself with `n-1` (moving to the previous row) and `(k+1)/2` (finding the corresponding position in the previous row). b. The result of the recursive call is stored in variable `a`. c. If `(k+1)%2` is 0, it means `k` is even. In this case, the function returns the value of `a` as it is. d. If `(k+1)%2` is 1, it means `k` is odd. In this case, the function returns the negation of `a` (1-a). By using recursion and dividing the problem into smaller subproblems, the function effectively calculates the value at position `k` in the `n`th row of the grammar sequence. Please note that the code assumes `n` and `k` are positive integers.

[@tradewise4097]

Coooooooooooooooooooooooooooooooooooooooooooooool !! Thik hai........................

[@tannusharma2285]

Thank u so much...u are awesome!!!

[@soniasingh532]

recursion is magic.

[@ankityadavxiia7267]

Thank you sir !

[@viggicodes]

class Solution: def kthGrammar(self, n: int, k: int) -> int: # base case if n==1 and k ==1 : return 0 length = 2 ** (n-1) mid = length / 2 if k mid: return 0 if (self.kthGrammar(n-1,k-mid)) else 1

[@deeptiyadav1879]

You are amazingg!!

[@vutukurisaiajay8133]

Why can’t we do N-1,k//2??