In the previous video, we have discussed the approach that we can take to solve this question, and
we have discussed what the recurrence relation or the recursive case is, and we have discussed the
base case.
Now, it's going to be pretty easy in this video to convert this into a pseudocode.
So let's go ahead and take a look at that.
So all we need to do is we need to write these two things into the code.
So let's say we have a function and let's call it k gram.
And all the inputs required should be provided to it.
And then inside the function let's write the base case.
So the base case was that if n is equal to one then we just need it to return zero.
So that's going to be our base case okay.
And the recursive case was that we need to find the length of the nth row.
So length would be two to the power n minus one.
For example over here when n is equal to one the length is two to the power zero which is one.
And when n is equal to two, the length is two to the power one, which is two.
So the length over here is equal to two to the power n minus one.
And then we need to find the midpoint, because we need to choose whether we can just find the kth symbol
in the previous row.
Or we need to take note of the k minus midpoint symbol in the previous row.
Right.
So we have seen that.
So let's find the midpoint which would be L divided by two.
And then we just need to check whether if k is less than half.
So less than equal to half.
If this is the case then all we need to do is return k gram which is this function itself.
So we are recursively calling the function itself with the inputs n minus one.
So that's the previous row and k itself because we have seen that if k is over here.
For example, if k is three then this is n is equal to four.
And this is n is equal to three.
So in this case if k is equal to three we have seen that four comma three n and k.
This over here is going to be equal to three comma three n and k right.
So that's what we have over here.
We are just returning k gram n minus one k.
And if this is not the case like for example if k is equal to seven then four comma seven.
We have seen that this is equal to not of three comma this seven over here minus the midpoint which
is four in this case.
So that's what we're going to write over here.
So if this is not the case then we're going to return k gram not of k gram.
This is the not part not of k gram n minus one k minus half.
So that's it.
So this is the pseudocode to solve the question.
Now.
Now let's go ahead and take a look at the complexity the time and space complexity of our recursive
solution.