1
00:00:00,110 --> 00:00:05,540
Let's now get into the code for the approach that we have discussed in the previous video.

2
00:00:05,540 --> 00:00:05,900
Okay.

3
00:00:05,900 --> 00:00:09,770
So the solution over here is going to be a recursive solution.

4
00:00:09,770 --> 00:00:13,370
So first let's go ahead and write the base case.

5
00:00:14,360 --> 00:00:17,870
And then we will also write the recursive case.

6
00:00:20,160 --> 00:00:20,670
All right.

7
00:00:20,670 --> 00:00:24,000
Now again, we have discussed that this is how the pattern evolves.

8
00:00:24,000 --> 00:00:28,800
So if n is equal to one then we just have zero in the expression.

9
00:00:28,800 --> 00:00:32,370
Now if n is equal to two then it's zero one.

10
00:00:32,370 --> 00:00:36,450
And we get this by replacing the previous zero with zero one.

11
00:00:36,450 --> 00:00:40,530
And over here notice for this zero we have zero one over here.

12
00:00:40,530 --> 00:00:44,250
And for this one over here we have one zero over here.

13
00:00:44,250 --> 00:00:47,700
Again we have discussed this in detail in the previous video.

14
00:00:47,700 --> 00:00:52,080
So the base case over here would be if n is equal to one.

15
00:00:52,080 --> 00:00:56,250
If that is the case then we just have to return zero okay.

16
00:00:56,250 --> 00:00:57,450
So that's the base case.

17
00:00:57,450 --> 00:00:58,800
So let's go ahead and write that.

18
00:00:58,800 --> 00:01:05,580
So if n is equal to one then we will just return zero okay.

19
00:01:05,580 --> 00:01:09,600
And again if n is equal to one k only can take the value one.

20
00:01:09,600 --> 00:01:12,900
Now let us go ahead now and write the recursive case.

21
00:01:13,380 --> 00:01:21,750
Now again in the recursive case we will try to recursively call the kth grammar function with a smaller

22
00:01:21,750 --> 00:01:24,930
input or an input closer to the base case.

23
00:01:24,930 --> 00:01:30,210
All right, now, as we have discussed in the previous video, first we will need to find the length

24
00:01:30,210 --> 00:01:34,500
of the expression or the length of the expression for the input value of n.

25
00:01:34,500 --> 00:01:35,970
So let me write over here.

26
00:01:35,970 --> 00:01:44,760
Let length is equal to math dot pow two to the power n minus one.

27
00:01:44,760 --> 00:01:49,710
Okay, so this would be the length of the expression for a particular value of n.

28
00:01:49,710 --> 00:01:55,170
And if this is the length then the mid value would be length divided by two.

29
00:01:56,160 --> 00:01:56,730
Okay.

30
00:01:56,730 --> 00:02:04,770
Now all that we need to do is we have to check whether k is less than or equal to the mid value okay.

31
00:02:04,770 --> 00:02:07,950
So if that is the case then we would do something.

32
00:02:07,950 --> 00:02:11,100
And if that's not the case we'd have to do something else.

33
00:02:11,100 --> 00:02:13,830
So again this is something that we have discussed in the previous video.

34
00:02:13,830 --> 00:02:14,760
So let's go ahead.

35
00:02:14,760 --> 00:02:21,360
So if k is less than the mid value or less than equal to the mid value, we have seen that the expression

36
00:02:21,360 --> 00:02:22,680
for the previous row.

37
00:02:22,680 --> 00:02:27,930
Again we need to find the value at the kth position in the nth row okay.

38
00:02:27,930 --> 00:02:34,830
So if k is less than the mid value because the first half for example over here we have n is equal to

39
00:02:34,830 --> 00:02:35,370
three.

40
00:02:35,370 --> 00:02:38,040
And this is the case where n is equal to two.

41
00:02:39,210 --> 00:02:46,770
So notice that when n is equal to three, the first half which is zero one is the same as the expression

42
00:02:46,770 --> 00:02:49,350
in the previous slide which is zero one itself.

43
00:02:49,350 --> 00:02:54,090
So if k is less than or equal to the mid value, it would be somewhere over here.

44
00:02:54,090 --> 00:02:57,240
Or in this example it would be either 1 or 2.

45
00:02:57,240 --> 00:03:04,530
And in that case we can reduce the input size or the value of n and we'll call the kth grammar function.

46
00:03:04,530 --> 00:03:08,190
So the inputs in this case would be n minus one and k.

47
00:03:08,190 --> 00:03:11,640
And we would just have to return this okay.

48
00:03:11,640 --> 00:03:15,600
So let's write return kth grammar n minus one and k.

49
00:03:15,600 --> 00:03:20,190
And again the reason is for the first half the expression in the previous row.

50
00:03:20,190 --> 00:03:23,910
And the current row looks exactly one and the same.

51
00:03:23,910 --> 00:03:30,000
And because k is less than equal to mid, if we want to find kth grammar n comma k, we just need to

52
00:03:30,000 --> 00:03:32,790
find kth grammar n minus one comma k.

53
00:03:32,790 --> 00:03:34,410
So that's what we are finding over here.

54
00:03:34,410 --> 00:03:35,760
And we will be returning.

55
00:03:35,760 --> 00:03:40,680
And again notice the input in this case is getting closer to the base case.

56
00:03:40,680 --> 00:03:47,760
Now if k is greater than the mid value we would still call the kth grammar function recursively.

57
00:03:47,760 --> 00:03:51,540
And in this case the input values would be n minus one.

58
00:03:51,540 --> 00:03:55,770
And as we have discussed k minus the mid value okay.

59
00:03:55,770 --> 00:03:57,150
And again we cannot return.

60
00:03:57,150 --> 00:04:00,960
This will have to do one minus whatever we get over here.

61
00:04:00,960 --> 00:04:04,650
Because if we get one over here we want to return zero.

62
00:04:04,650 --> 00:04:08,730
And if we get zero over here we want to get one or we want to return one.

63
00:04:08,730 --> 00:04:12,960
So to achieve that we will return one minus kth grammar.

64
00:04:12,960 --> 00:04:17,160
And the inputs in this case would be n minus one and k minus mid.

65
00:04:17,190 --> 00:04:21,060
Notice that in this case also we are getting closer to the base case.

66
00:04:21,060 --> 00:04:24,630
So this is how we can solve the kth grammar question.

67
00:04:24,630 --> 00:04:29,010
Now let's go ahead and run this code and see if it's passing all the test cases.

68
00:04:34,760 --> 00:04:37,940
And you can see that it's passing all the test cases.

69
00:04:37,940 --> 00:04:40,040
Again, do make use of the user logs.

70
00:04:40,040 --> 00:04:43,610
It will help you debug your code in case you're stuck at some point.