Let's now get into the code for the approach that we have discussed in the previous video.
Okay.
So the solution over here is going to be a recursive solution.
So first let's go ahead and write the base case.
And then we will also write the recursive case.
All right.
Now again, we have discussed that this is how the pattern evolves.
So if n is equal to one then we just have zero in the expression.
Now if n is equal to two then it's zero one.
And we get this by replacing the previous zero with zero one.
And over here notice for this zero we have zero one over here.
And for this one over here we have one zero over here.
Again we have discussed this in detail in the previous video.
So the base case over here would be if n is equal to one.
If that is the case then we just have to return zero okay.
So that's the base case.
So let's go ahead and write that.
So if n is equal to one then we will just return zero okay.
And again if n is equal to one k only can take the value one.
Now let us go ahead now and write the recursive case.
Now again in the recursive case we will try to recursively call the kth grammar function with a smaller
input or an input closer to the base case.
All right, now, as we have discussed in the previous video, first we will need to find the length
of the expression or the length of the expression for the input value of n.
So let me write over here.
Let length is equal to math dot pow two to the power n minus one.
Okay, so this would be the length of the expression for a particular value of n.
And if this is the length then the mid value would be length divided by two.
Okay.
Now all that we need to do is we have to check whether k is less than or equal to the mid value okay.
So if that is the case then we would do something.
And if that's not the case we'd have to do something else.
So again this is something that we have discussed in the previous video.
So let's go ahead.
So if k is less than the mid value or less than equal to the mid value, we have seen that the expression
for the previous row.
Again we need to find the value at the kth position in the nth row okay.
So if k is less than the mid value because the first half for example over here we have n is equal to
three.
And this is the case where n is equal to two.
So notice that when n is equal to three, the first half which is zero one is the same as the expression
in the previous slide which is zero one itself.
So if k is less than or equal to the mid value, it would be somewhere over here.
Or in this example it would be either 1 or 2.
And in that case we can reduce the input size or the value of n and we'll call the kth grammar function.
So the inputs in this case would be n minus one and k.
And we would just have to return this okay.
So let's write return kth grammar n minus one and k.
And again the reason is for the first half the expression in the previous row.
And the current row looks exactly one and the same.
And because k is less than equal to mid, if we want to find kth grammar n comma k, we just need to
find kth grammar n minus one comma k.
So that's what we are finding over here.
And we will be returning.
And again notice the input in this case is getting closer to the base case.
Now if k is greater than the mid value we would still call the kth grammar function recursively.
And in this case the input values would be n minus one.
And as we have discussed k minus the mid value okay.
And again we cannot return.
This will have to do one minus whatever we get over here.
Because if we get one over here we want to return zero.
And if we get zero over here we want to get one or we want to return one.
So to achieve that we will return one minus kth grammar.
And the inputs in this case would be n minus one and k minus mid.
Notice that in this case also we are getting closer to the base case.
So this is how we can solve the kth grammar question.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's passing all the test cases.
Again, do make use of the user logs.
It will help you debug your code in case you're stuck at some point.