In the previous video, we have understood the problem statement and we have come up with some interesting
test cases.
Now let's get started and let's try to think of how we can solve this question.
Over here we have written down the sequence.
So this is the case where n is equal to one.
This is when n is equal to two.
So let me write that over here.
This is n is equal to three.
And this is n is equal to four.
Now remember how we discussed how we can come up with this pattern.
Right.
For example if we know the sequence for n is equal to three to come up with the sequence for n is equal
to four, we take every character over here, or every value in n is equal to three.
And for every zero we write zero one, and for every one we write one zero.
So that's how we come up with the next sequence.
So notice how the question itself is defined recursively.
So the question itself is defined recursively which is a strong indication that we can approach this
question.
And we can solve this question using recursion.
So let's get started.
If we want to write a recursive solution for this question, there are basically two scenarios that
we need to think of, which is the base case and the recursive case or the recurrence relation involved.
Remember we have discussed that the recurrence relation is nothing but expressing the solution of a
problem as a function of the solutions to smaller instances of the same problem.
Right.
So that's what the recurrence relation is all about.
Now let's begin by taking a look at the sequence over here and by identifying some interesting observations.
The first observation over here is that for any row, the first half of that row is equal to the previous
row.
Right.
For example, this is n is equal to four.
So let's write that over here.
So this is n is equal to four.
And this is n is equal to three.
Notice that for n is equal to four the first half is equal to the sequence as if n is equal to three.
So the same thing is repeated over here.
So this is the first interesting observation.
And again that's true throughout the sequence.
Right.
So let's take a look at this part over here.
So we have zero one over here.
And the first half of n is equal to three is also zero one.
So this is an interesting observation.
Now is there any other observation to make.
You can see that for this row over here, the second half which is this part over here is actually not
of the previous row.
Right.
So for every zero over here right one.
So we have zero over here.
So we take naught of zero which is one.
And we have one over here.
We take naught of one which is zero.
And then you keep doing that.
So you have one over here.
So you get zero over here and you have zero over here.
So you get one over here.
So for the nth row the second half is not of the previous row.
Now this is true for every row right.
So again let's take a look at that.
So we have not of this over here which is the second half of the nth row.
Now over here we have zero and one.
So if I take naught of zero I get one.
And if I take naught of one I get zero.
So this is an interesting observation because this helps us to break down the problem.
Now if I want to find the kth symbol at row n, I just need to find.
The previous solution.
So that's rho n minus one.
And then I need to choose based on what the value of k is.
Because if the value of k is less than or equal to the half of, uh, the length of the nth row, which
is this, for example, this case, if it's let's say 2 or 3, this would be two.
This is three.
Then notice that I just need to find the kth symbol in the n minus one row itself, because this would
be equal right.
So again, if I knew the answer of a smaller problem, I can use it to solve the bigger problem.
So if using this, if I want to find n comma k, then if k is less than half of the length of the nth
row, then I would just need to find n minus one k, right.
And if that's not the case, if k is over here, like let's say k is 7 or 8.
In that case I would just need to find n minus one comma k minus the mid value.
Because again you need to convert this to something over here.
Right.
So let's say we want to find k for seven.
So the mid value over here is four and seven minus four gives you three.
And at three you have one over here.
So n minus one k minus mid.
This over here would give us one.
But we need zero over here.
Right.
So you just need to take note of this right.
So you just need to take note of this.
Or you can think of it as taking as one minus this value over here.
So one minus one gives us zero or not of one also gives us zero.
So in this way you can see that we can approach this question using recursion.
Now when do we stop.
Right.
Again we we we are saying that if we want to find n comma k we proceed and find something from n minus
one and again, because we are doing it recursively when we're trying to find the value the kth, the
value at the kth index for n minus one, we would go to n minus two.
And we would keep doing this till we reach the base or terminating condition.
So that's the second thing that we need to be aware of.
So the base or the terminating condition over here.
Can be thought of, as we've discussed previously, in two easy ways.
Just try to think of the last valid case or the first invalid case.
Again, we have seen that this can be done in either way.
Again, it depends on the question at hand, whichever is more convenient.
Now over here it's pretty straightforward that the last valid case is when n is equal to one, right.
So this is the last valid case because you can't have n is equal to zero.
There's there's no sequence for that.
Right.
So that's how the question is defined.
So the last valid case over here is n is equal to one.
And what would we return.
If n is equal to one the output would invariably be zero because we just have k is equal to one if n
is equal to one.
So there is nothing else in this sequence.
So the base case is the last valid case over here, which is if n is equal to one we'll just return
zero.
And with this we have sufficient understanding to go ahead and write the pseudocode for this solution.
Let's quickly summarize our approach before we go ahead and take a look at the pseudocode.
So again the base case is very clear.
If n is equal to one just return zero.
And let's say we want to find let's say this is index seven when it's one indexed.
And let's say n is equal to four.
So let's say the question is find the symbol over here at four n is equal to four.
And let's say k is given as seven.
So let's quickly do a dry run of how our recursive solution would approach this.
So for finding four comma seven where n is four and k is seven, we would go ahead and take a look at
the n minus one th row which is this row over here.
Now the length of the row over here at index four.
Again this is one index.
The length over here is eight.
Let me write that over here.
Length is eight.
Now the midpoint of this would be eight by two which is equal to four.
And because k is greater than the midpoint and we know that it's over here.
So we know that we need to find not of the corresponding value in the previous row.
So first let's find the corresponding value over here.
For that we just need to do seven minus four which is equal to three.
So we are going to find out n minus one three.
So this is 123.
So n minus one three is equal to one.
And we are going to just take note of this.
Right.
So n minus one comma three will give us one.
And when we take note of that we would get to zero.
So that's how we will approach this question.
Right.
And again let's quickly complete the dry run.
Now if we want n minus one comma three what would we do.
Again recursively we would go to n minus two which is this over here which is n is equal to two.
Right.
Again we have not hit the base condition which is n is equal to one yet.
So for finding this again let me write that over here we have we went to N minus one which was three
itself.
Right now to find three comma three we would again go to the previous row which is two again two comma.
What value.
Again let's try to think of it.
So in this case three is this value over here.
And it's larger than midway.
Right over here.
Midway is two.
It's larger than mid the mid point over here.
Therefore we have to do three minus the mid point which is three minus two which is equal to one.
So we have to find two comma one.
So n is equal to two and k is equal to one.
And because we went over here because this is above the mid point we have to do not of this.
Let's just think of how the recursive solution would find it.
Now to find two comma one the code would go ahead and find one two minus one is one one comma.
And then over here this is two comma one and one is above the half point right.
It's the mid point over here is one itself.
So over here this is one right.
Sorry.
This is one.
This is two.
So at this point we have one over here.
So we don't need to go to the case where we find naught.
We just need one itself from the previous row, because we know that the half part of any row is the
same as the previous row.
So to find two comma one, our code would just go ahead and find one comma one where n is equal to one
and k is equal to one.
Now at this point our code would start returning because one comma one we know that that's equal to
zero.
So one comma one is zero.
So this over here is zero okay.
So this over here is zero.
Therefore two comma one two comma one would be not of zero which is one.
So this over here would be one.
And we know that three comma three is one.
And to find this value we would just need to find naught of one which is zero.
And that's this zero over here.
So that is how the recursive solution would work.
So we have just traced the algorithm.
And notice over here this over here is the recursion tree.
The first call over here is four comma seven.
That would again recursively call three comma three which would recursively call two comma one.
And again it would call one comma one.
And then it would start returning.
So one comma one return zero.
And this over here becomes not of zero which is one.
So this will return one.
And this over here will become not of one which is zero.
So this would return zero.
Right.
So four comma seven in this way would give us the answer as zero.
So this is how the recursive solution would work.
Now you could also try go ahead and uh write the uh recursive call stack if that's helpful.
Again it would be the same thing.
Right.
Let me just quickly write that over here.
It would be again you have four comma seven over here.
And then you have three comma three over here, two comma one over here and one comma one over here.
And then this would pop and it would return.
And it would, it would go on in this way.
So this is the approach that we will follow to solve this question.