1
00:00:00,600 --> 00:00:06,840
In the previous video, we have discussed the approach that we can take to solve this question, and

2
00:00:06,840 --> 00:00:12,510
we have discussed what the recurrence relation or the recursive case is, and we have discussed the

3
00:00:12,510 --> 00:00:13,320
base case.

4
00:00:13,350 --> 00:00:19,380
Now, it's going to be pretty easy in this video to convert this into a pseudocode.

5
00:00:19,380 --> 00:00:21,540
So let's go ahead and take a look at that.

6
00:00:21,540 --> 00:00:25,830
So all we need to do is we need to write these two things into the code.

7
00:00:25,830 --> 00:00:30,180
So let's say we have a function and let's call it k gram.

8
00:00:30,840 --> 00:00:34,440
And all the inputs required should be provided to it.

9
00:00:34,440 --> 00:00:38,370
And then inside the function let's write the base case.

10
00:00:38,370 --> 00:00:44,940
So the base case was that if n is equal to one then we just need it to return zero.

11
00:00:44,940 --> 00:00:48,570
So that's going to be our base case okay.

12
00:00:48,570 --> 00:00:55,800
And the recursive case was that we need to find the length of the nth row.

13
00:00:55,800 --> 00:00:59,280
So length would be two to the power n minus one.

14
00:00:59,280 --> 00:01:05,070
For example over here when n is equal to one the length is two to the power zero which is one.

15
00:01:05,070 --> 00:01:09,720
And when n is equal to two, the length is two to the power one, which is two.

16
00:01:09,720 --> 00:01:14,190
So the length over here is equal to two to the power n minus one.

17
00:01:14,190 --> 00:01:21,480
And then we need to find the midpoint, because we need to choose whether we can just find the kth symbol

18
00:01:21,480 --> 00:01:22,920
in the previous row.

19
00:01:22,920 --> 00:01:29,280
Or we need to take note of the k minus midpoint symbol in the previous row.

20
00:01:29,280 --> 00:01:29,550
Right.

21
00:01:29,550 --> 00:01:30,480
So we have seen that.

22
00:01:30,480 --> 00:01:34,920
So let's find the midpoint which would be L divided by two.

23
00:01:35,430 --> 00:01:40,320
And then we just need to check whether if k is less than half.

24
00:01:40,320 --> 00:01:42,480
So less than equal to half.

25
00:01:42,480 --> 00:01:49,020
If this is the case then all we need to do is return k gram which is this function itself.

26
00:01:49,020 --> 00:01:54,120
So we are recursively calling the function itself with the inputs n minus one.

27
00:01:54,120 --> 00:02:00,180
So that's the previous row and k itself because we have seen that if k is over here.

28
00:02:00,180 --> 00:02:04,320
For example, if k is three then this is n is equal to four.

29
00:02:04,320 --> 00:02:06,090
And this is n is equal to three.

30
00:02:06,090 --> 00:02:14,190
So in this case if k is equal to three we have seen that four comma three n and k.

31
00:02:14,220 --> 00:02:20,070
This over here is going to be equal to three comma three n and k right.

32
00:02:20,070 --> 00:02:21,690
So that's what we have over here.

33
00:02:21,690 --> 00:02:25,110
We are just returning k gram n minus one k.

34
00:02:25,110 --> 00:02:31,830
And if this is not the case like for example if k is equal to seven then four comma seven.

35
00:02:32,040 --> 00:02:41,700
We have seen that this is equal to not of three comma this seven over here minus the midpoint which

36
00:02:41,700 --> 00:02:43,290
is four in this case.

37
00:02:43,290 --> 00:02:45,450
So that's what we're going to write over here.

38
00:02:45,450 --> 00:02:52,170
So if this is not the case then we're going to return k gram not of k gram.

39
00:02:52,170 --> 00:02:58,290
This is the not part not of k gram n minus one k minus half.

40
00:02:58,290 --> 00:02:59,190
So that's it.

41
00:02:59,190 --> 00:03:01,590
So this is the pseudocode to solve the question.

42
00:03:01,590 --> 00:03:02,100
Now.

43
00:03:02,100 --> 00:03:08,850
Now let's go ahead and take a look at the complexity the time and space complexity of our recursive

44
00:03:08,850 --> 00:03:09,630
solution.