1
00:00:00,500 --> 00:00:07,220
In the previous video, we have understood the problem statement and we have come up with some interesting

2
00:00:07,250 --> 00:00:08,180
test cases.

3
00:00:08,210 --> 00:00:13,520
Now let's get started and let's try to think of how we can solve this question.

4
00:00:13,550 --> 00:00:16,370
Over here we have written down the sequence.

5
00:00:16,370 --> 00:00:19,010
So this is the case where n is equal to one.

6
00:00:19,010 --> 00:00:21,050
This is when n is equal to two.

7
00:00:21,080 --> 00:00:22,700
So let me write that over here.

8
00:00:22,700 --> 00:00:24,380
This is n is equal to three.

9
00:00:24,380 --> 00:00:26,090
And this is n is equal to four.

10
00:00:26,120 --> 00:00:30,770
Now remember how we discussed how we can come up with this pattern.

11
00:00:30,770 --> 00:00:31,130
Right.

12
00:00:31,130 --> 00:00:37,460
For example if we know the sequence for n is equal to three to come up with the sequence for n is equal

13
00:00:37,460 --> 00:00:42,710
to four, we take every character over here, or every value in n is equal to three.

14
00:00:42,710 --> 00:00:47,990
And for every zero we write zero one, and for every one we write one zero.

15
00:00:47,990 --> 00:00:50,810
So that's how we come up with the next sequence.

16
00:00:51,170 --> 00:00:57,110
So notice how the question itself is defined recursively.

17
00:00:57,110 --> 00:01:04,190
So the question itself is defined recursively which is a strong indication that we can approach this

18
00:01:04,190 --> 00:01:04,820
question.

19
00:01:04,820 --> 00:01:08,240
And we can solve this question using recursion.

20
00:01:08,240 --> 00:01:09,800
So let's get started.

21
00:01:09,800 --> 00:01:16,760
If we want to write a recursive solution for this question, there are basically two scenarios that

22
00:01:16,760 --> 00:01:24,170
we need to think of, which is the base case and the recursive case or the recurrence relation involved.

23
00:01:24,170 --> 00:01:32,270
Remember we have discussed that the recurrence relation is nothing but expressing the solution of a

24
00:01:32,270 --> 00:01:39,140
problem as a function of the solutions to smaller instances of the same problem.

25
00:01:39,140 --> 00:01:39,530
Right.

26
00:01:39,530 --> 00:01:42,080
So that's what the recurrence relation is all about.

27
00:01:42,080 --> 00:01:52,010
Now let's begin by taking a look at the sequence over here and by identifying some interesting observations.

28
00:01:52,870 --> 00:02:02,470
The first observation over here is that for any row, the first half of that row is equal to the previous

29
00:02:02,470 --> 00:02:02,950
row.

30
00:02:02,980 --> 00:02:03,430
Right.

31
00:02:03,430 --> 00:02:05,770
For example, this is n is equal to four.

32
00:02:05,770 --> 00:02:06,790
So let's write that over here.

33
00:02:06,790 --> 00:02:08,350
So this is n is equal to four.

34
00:02:08,350 --> 00:02:10,120
And this is n is equal to three.

35
00:02:10,150 --> 00:02:19,990
Notice that for n is equal to four the first half is equal to the sequence as if n is equal to three.

36
00:02:19,990 --> 00:02:22,990
So the same thing is repeated over here.

37
00:02:23,020 --> 00:02:25,540
So this is the first interesting observation.

38
00:02:25,540 --> 00:02:28,150
And again that's true throughout the sequence.

39
00:02:28,150 --> 00:02:28,390
Right.

40
00:02:28,390 --> 00:02:30,700
So let's take a look at this part over here.

41
00:02:30,700 --> 00:02:32,260
So we have zero one over here.

42
00:02:32,260 --> 00:02:36,640
And the first half of n is equal to three is also zero one.

43
00:02:36,640 --> 00:02:39,010
So this is an interesting observation.

44
00:02:39,010 --> 00:02:42,100
Now is there any other observation to make.

45
00:02:42,100 --> 00:02:51,550
You can see that for this row over here, the second half which is this part over here is actually not

46
00:02:51,550 --> 00:02:52,870
of the previous row.

47
00:02:52,870 --> 00:02:53,230
Right.

48
00:02:53,230 --> 00:02:56,350
So for every zero over here right one.

49
00:02:56,350 --> 00:02:57,700
So we have zero over here.

50
00:02:57,700 --> 00:03:00,490
So we take naught of zero which is one.

51
00:03:00,490 --> 00:03:01,840
And we have one over here.

52
00:03:01,840 --> 00:03:04,450
We take naught of one which is zero.

53
00:03:04,450 --> 00:03:05,650
And then you keep doing that.

54
00:03:05,650 --> 00:03:06,640
So you have one over here.

55
00:03:06,640 --> 00:03:09,580
So you get zero over here and you have zero over here.

56
00:03:09,580 --> 00:03:11,350
So you get one over here.

57
00:03:11,350 --> 00:03:18,100
So for the nth row the second half is not of the previous row.

58
00:03:18,610 --> 00:03:20,710
Now this is true for every row right.

59
00:03:20,710 --> 00:03:22,330
So again let's take a look at that.

60
00:03:22,330 --> 00:03:26,680
So we have not of this over here which is the second half of the nth row.

61
00:03:26,680 --> 00:03:28,420
Now over here we have zero and one.

62
00:03:28,420 --> 00:03:30,820
So if I take naught of zero I get one.

63
00:03:30,820 --> 00:03:33,910
And if I take naught of one I get zero.

64
00:03:33,910 --> 00:03:40,030
So this is an interesting observation because this helps us to break down the problem.

65
00:03:40,030 --> 00:03:49,000
Now if I want to find the kth symbol at row n, I just need to find.

66
00:03:49,520 --> 00:03:51,380
The previous solution.

67
00:03:51,380 --> 00:03:53,570
So that's rho n minus one.

68
00:03:53,570 --> 00:03:58,850
And then I need to choose based on what the value of k is.

69
00:03:58,850 --> 00:04:07,160
Because if the value of k is less than or equal to the half of, uh, the length of the nth row, which

70
00:04:07,160 --> 00:04:11,960
is this, for example, this case, if it's let's say 2 or 3, this would be two.

71
00:04:11,960 --> 00:04:12,920
This is three.

72
00:04:12,920 --> 00:04:22,640
Then notice that I just need to find the kth symbol in the n minus one row itself, because this would

73
00:04:22,640 --> 00:04:23,870
be equal right.

74
00:04:23,870 --> 00:04:29,600
So again, if I knew the answer of a smaller problem, I can use it to solve the bigger problem.

75
00:04:29,600 --> 00:04:39,800
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

76
00:04:39,800 --> 00:04:44,600
row, then I would just need to find n minus one k, right.

77
00:04:44,600 --> 00:04:49,730
And if that's not the case, if k is over here, like let's say k is 7 or 8.

78
00:04:49,730 --> 00:04:57,380
In that case I would just need to find n minus one comma k minus the mid value.

79
00:04:57,380 --> 00:05:00,590
Because again you need to convert this to something over here.

80
00:05:00,590 --> 00:05:00,890
Right.

81
00:05:00,890 --> 00:05:03,770
So let's say we want to find k for seven.

82
00:05:03,770 --> 00:05:09,200
So the mid value over here is four and seven minus four gives you three.

83
00:05:09,860 --> 00:05:12,590
And at three you have one over here.

84
00:05:12,590 --> 00:05:15,620
So n minus one k minus mid.

85
00:05:15,620 --> 00:05:17,480
This over here would give us one.

86
00:05:17,480 --> 00:05:18,800
But we need zero over here.

87
00:05:18,800 --> 00:05:19,100
Right.

88
00:05:19,100 --> 00:05:22,640
So you just need to take note of this right.

89
00:05:22,640 --> 00:05:25,010
So you just need to take note of this.

90
00:05:25,010 --> 00:05:29,120
Or you can think of it as taking as one minus this value over here.

91
00:05:29,120 --> 00:05:34,100
So one minus one gives us zero or not of one also gives us zero.

92
00:05:34,100 --> 00:05:39,590
So in this way you can see that we can approach this question using recursion.

93
00:05:39,590 --> 00:05:41,870
Now when do we stop.

94
00:05:41,870 --> 00:05:42,140
Right.

95
00:05:42,140 --> 00:05:48,830
Again we we we are saying that if we want to find n comma k we proceed and find something from n minus

96
00:05:48,830 --> 00:05:56,450
one and again, because we are doing it recursively when we're trying to find the value the kth, the

97
00:05:56,450 --> 00:06:00,500
value at the kth index for n minus one, we would go to n minus two.

98
00:06:00,500 --> 00:06:06,020
And we would keep doing this till we reach the base or terminating condition.

99
00:06:06,020 --> 00:06:08,660
So that's the second thing that we need to be aware of.

100
00:06:08,660 --> 00:06:12,080
So the base or the terminating condition over here.

101
00:06:12,740 --> 00:06:17,870
Can be thought of, as we've discussed previously, in two easy ways.

102
00:06:17,870 --> 00:06:24,740
Just try to think of the last valid case or the first invalid case.

103
00:06:24,740 --> 00:06:29,150
Again, we have seen that this can be done in either way.

104
00:06:29,150 --> 00:06:33,140
Again, it depends on the question at hand, whichever is more convenient.

105
00:06:33,140 --> 00:06:41,930
Now over here it's pretty straightforward that the last valid case is when n is equal to one, right.

106
00:06:41,930 --> 00:06:45,830
So this is the last valid case because you can't have n is equal to zero.

107
00:06:45,830 --> 00:06:47,540
There's there's no sequence for that.

108
00:06:47,540 --> 00:06:47,720
Right.

109
00:06:47,720 --> 00:06:50,060
So that's how the question is defined.

110
00:06:50,060 --> 00:06:54,470
So the last valid case over here is n is equal to one.

111
00:06:54,470 --> 00:06:56,360
And what would we return.

112
00:06:56,360 --> 00:07:04,610
If n is equal to one the output would invariably be zero because we just have k is equal to one if n

113
00:07:04,610 --> 00:07:05,300
is equal to one.

114
00:07:05,300 --> 00:07:07,340
So there is nothing else in this sequence.

115
00:07:07,340 --> 00:07:15,110
So the base case is the last valid case over here, which is if n is equal to one we'll just return

116
00:07:15,110 --> 00:07:15,800
zero.

117
00:07:15,800 --> 00:07:22,880
And with this we have sufficient understanding to go ahead and write the pseudocode for this solution.

118
00:07:22,880 --> 00:07:28,670
Let's quickly summarize our approach before we go ahead and take a look at the pseudocode.

119
00:07:28,670 --> 00:07:31,220
So again the base case is very clear.

120
00:07:31,220 --> 00:07:34,070
If n is equal to one just return zero.

121
00:07:34,070 --> 00:07:40,820
And let's say we want to find let's say this is index seven when it's one indexed.

122
00:07:40,820 --> 00:07:43,220
And let's say n is equal to four.

123
00:07:43,220 --> 00:07:49,400
So let's say the question is find the symbol over here at four n is equal to four.

124
00:07:49,400 --> 00:07:52,070
And let's say k is given as seven.

125
00:07:52,970 --> 00:07:58,280
So let's quickly do a dry run of how our recursive solution would approach this.

126
00:07:58,280 --> 00:08:05,660
So for finding four comma seven where n is four and k is seven, we would go ahead and take a look at

127
00:08:05,660 --> 00:08:09,590
the n minus one th row which is this row over here.

128
00:08:09,590 --> 00:08:14,570
Now the length of the row over here at index four.

129
00:08:14,570 --> 00:08:15,920
Again this is one index.

130
00:08:15,920 --> 00:08:17,990
The length over here is eight.

131
00:08:18,530 --> 00:08:19,760
Let me write that over here.

132
00:08:19,760 --> 00:08:21,110
Length is eight.

133
00:08:21,140 --> 00:08:26,030
Now the midpoint of this would be eight by two which is equal to four.

134
00:08:26,030 --> 00:08:31,160
And because k is greater than the midpoint and we know that it's over here.

135
00:08:31,160 --> 00:08:38,150
So we know that we need to find not of the corresponding value in the previous row.

136
00:08:38,150 --> 00:08:41,270
So first let's find the corresponding value over here.

137
00:08:41,270 --> 00:08:46,820
For that we just need to do seven minus four which is equal to three.

138
00:08:47,330 --> 00:08:50,690
So we are going to find out n minus one three.

139
00:08:50,690 --> 00:08:52,460
So this is 123.

140
00:08:52,460 --> 00:08:55,370
So n minus one three is equal to one.

141
00:08:55,370 --> 00:08:58,610
And we are going to just take note of this.

142
00:09:01,580 --> 00:09:02,120
Right.

143
00:09:02,120 --> 00:09:04,760
So n minus one comma three will give us one.

144
00:09:04,760 --> 00:09:08,630
And when we take note of that we would get to zero.

145
00:09:08,630 --> 00:09:10,670
So that's how we will approach this question.

146
00:09:10,670 --> 00:09:11,030
Right.

147
00:09:11,030 --> 00:09:13,370
And again let's quickly complete the dry run.

148
00:09:13,370 --> 00:09:17,300
Now if we want n minus one comma three what would we do.

149
00:09:17,300 --> 00:09:23,570
Again recursively we would go to n minus two which is this over here which is n is equal to two.

150
00:09:23,570 --> 00:09:23,960
Right.

151
00:09:23,960 --> 00:09:27,560
Again we have not hit the base condition which is n is equal to one yet.

152
00:09:27,560 --> 00:09:32,720
So for finding this again let me write that over here we have we went to N minus one which was three

153
00:09:32,720 --> 00:09:33,050
itself.

154
00:09:33,050 --> 00:09:41,180
Right now to find three comma three we would again go to the previous row which is two again two comma.

155
00:09:41,180 --> 00:09:41,990
What value.

156
00:09:41,990 --> 00:09:43,730
Again let's try to think of it.

157
00:09:43,730 --> 00:09:47,330
So in this case three is this value over here.

158
00:09:47,330 --> 00:09:49,910
And it's larger than midway.

159
00:09:49,910 --> 00:09:50,480
Right over here.

160
00:09:50,480 --> 00:09:51,440
Midway is two.

161
00:09:51,470 --> 00:09:54,500
It's larger than mid the mid point over here.

162
00:09:54,500 --> 00:10:01,310
Therefore we have to do three minus the mid point which is three minus two which is equal to one.

163
00:10:01,310 --> 00:10:03,590
So we have to find two comma one.

164
00:10:03,590 --> 00:10:07,160
So n is equal to two and k is equal to one.

165
00:10:07,160 --> 00:10:12,770
And because we went over here because this is above the mid point we have to do not of this.

166
00:10:13,070 --> 00:10:17,240
Let's just think of how the recursive solution would find it.

167
00:10:17,240 --> 00:10:25,550
Now to find two comma one the code would go ahead and find one two minus one is one one comma.

168
00:10:25,550 --> 00:10:31,370
And then over here this is two comma one and one is above the half point right.

169
00:10:31,370 --> 00:10:33,890
It's the mid point over here is one itself.

170
00:10:33,890 --> 00:10:36,260
So over here this is one right.

171
00:10:36,260 --> 00:10:36,560
Sorry.

172
00:10:36,560 --> 00:10:37,190
This is one.

173
00:10:37,190 --> 00:10:37,970
This is two.

174
00:10:38,700 --> 00:10:41,430
So at this point we have one over here.

175
00:10:41,430 --> 00:10:45,870
So we don't need to go to the case where we find naught.

176
00:10:45,870 --> 00:10:53,700
We just need one itself from the previous row, because we know that the half part of any row is the

177
00:10:53,700 --> 00:10:55,320
same as the previous row.

178
00:10:55,320 --> 00:11:02,070
So to find two comma one, our code would just go ahead and find one comma one where n is equal to one

179
00:11:02,070 --> 00:11:03,240
and k is equal to one.

180
00:11:03,240 --> 00:11:09,930
Now at this point our code would start returning because one comma one we know that that's equal to

181
00:11:09,930 --> 00:11:10,440
zero.

182
00:11:10,440 --> 00:11:12,630
So one comma one is zero.

183
00:11:12,630 --> 00:11:14,880
So this over here is zero okay.

184
00:11:14,880 --> 00:11:17,040
So this over here is zero.

185
00:11:17,040 --> 00:11:22,890
Therefore two comma one two comma one would be not of zero which is one.

186
00:11:22,890 --> 00:11:25,770
So this over here would be one.

187
00:11:25,770 --> 00:11:28,590
And we know that three comma three is one.

188
00:11:28,590 --> 00:11:33,090
And to find this value we would just need to find naught of one which is zero.

189
00:11:33,090 --> 00:11:35,190
And that's this zero over here.

190
00:11:35,190 --> 00:11:39,480
So that is how the recursive solution would work.

191
00:11:39,480 --> 00:11:41,670
So we have just traced the algorithm.

192
00:11:41,670 --> 00:11:45,150
And notice over here this over here is the recursion tree.

193
00:11:45,360 --> 00:11:47,820
The first call over here is four comma seven.

194
00:11:47,820 --> 00:11:53,310
That would again recursively call three comma three which would recursively call two comma one.

195
00:11:53,310 --> 00:11:55,530
And again it would call one comma one.

196
00:11:55,530 --> 00:11:57,210
And then it would start returning.

197
00:11:57,210 --> 00:11:59,100
So one comma one return zero.

198
00:11:59,100 --> 00:12:02,550
And this over here becomes not of zero which is one.

199
00:12:02,550 --> 00:12:04,170
So this will return one.

200
00:12:04,170 --> 00:12:07,830
And this over here will become not of one which is zero.

201
00:12:07,830 --> 00:12:09,240
So this would return zero.

202
00:12:09,240 --> 00:12:09,690
Right.

203
00:12:09,690 --> 00:12:13,950
So four comma seven in this way would give us the answer as zero.

204
00:12:13,950 --> 00:12:17,280
So this is how the recursive solution would work.

205
00:12:17,280 --> 00:12:23,910
Now you could also try go ahead and uh write the uh recursive call stack if that's helpful.

206
00:12:23,910 --> 00:12:25,080
Again it would be the same thing.

207
00:12:25,080 --> 00:12:25,260
Right.

208
00:12:25,260 --> 00:12:27,030
Let me just quickly write that over here.

209
00:12:27,030 --> 00:12:30,540
It would be again you have four comma seven over here.

210
00:12:30,540 --> 00:12:36,870
And then you have three comma three over here, two comma one over here and one comma one over here.

211
00:12:36,870 --> 00:12:39,060
And then this would pop and it would return.

212
00:12:39,060 --> 00:12:40,890
And it would, it would go on in this way.

213
00:12:40,890 --> 00:12:44,760
So this is the approach that we will follow to solve this question.