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

2
00:00:04,910 --> 00:00:11,930
So basically we are going to use the answer to a smaller problem to solve the bigger problem.

3
00:00:11,930 --> 00:00:13,250
So that's what we have discussed.

4
00:00:13,250 --> 00:00:13,640
Right.

5
00:00:13,640 --> 00:00:16,550
So again this is going to be a recursive solution.

6
00:00:16,550 --> 00:00:18,830
So let's write the skeleton of the solution.

7
00:00:18,830 --> 00:00:21,950
And then we'll go ahead and write the details of it okay.

8
00:00:21,950 --> 00:00:24,080
Now we will need a helper function.

9
00:00:24,080 --> 00:00:27,470
And let's just call that function Josephus itself.

10
00:00:28,190 --> 00:00:28,880
Okay.

11
00:00:28,880 --> 00:00:33,560
And to this function a particular value of n would be passed.

12
00:00:33,560 --> 00:00:35,600
So let's call it n itself.

13
00:00:35,600 --> 00:00:38,930
And finally we will have to call this function.

14
00:00:38,930 --> 00:00:44,540
So that's Josephus and will be passing this value of n which is given to us over here.

15
00:00:44,660 --> 00:00:50,750
And we will be getting back the index of the person who is the winner.

16
00:00:50,750 --> 00:00:57,290
And because we typically don't start to count with zero, therefore over here we will have to add one

17
00:00:57,290 --> 00:00:59,030
and this can be returned.

18
00:01:00,380 --> 00:01:00,770
Okay.

19
00:01:00,770 --> 00:01:02,630
So this is the skeleton of the solution.

20
00:01:02,630 --> 00:01:05,600
And we have discussed this in detail in the previous video.

21
00:01:05,600 --> 00:01:08,180
As in why we have to add one over here.

22
00:01:08,180 --> 00:01:11,840
Now let's go ahead and write the details of the helper function.

23
00:01:11,840 --> 00:01:18,260
So we will be writing the base case as well as the recursive case over here okay.

24
00:01:18,260 --> 00:01:23,360
Now the base case will be the scenario where n is equal to one.

25
00:01:23,360 --> 00:01:31,040
Now if there is just one person, then the self index position will be zero and we will be just returning

26
00:01:31,040 --> 00:01:31,370
that.

27
00:01:31,370 --> 00:01:36,770
So I can say if n is equal to one.

28
00:01:37,040 --> 00:01:40,460
So if this is the case we will just return zero.

29
00:01:40,460 --> 00:01:43,610
And over here when we get zero we will add one to it.

30
00:01:43,610 --> 00:01:47,540
So which means that the first person is the safe person okay.

31
00:01:47,540 --> 00:01:48,920
So that's done.

32
00:01:48,920 --> 00:01:51,650
Now let's go ahead and take a look at the recursive case.

33
00:01:51,830 --> 00:01:57,230
Now in the recursive case remember the approach that we are following over here is that we are using

34
00:01:57,230 --> 00:02:02,600
the answer to a smaller problem to find the answer to the original problem.

35
00:02:02,600 --> 00:02:10,190
So the answer to the smaller problem over here, when we are dealing with the problem of size n would

36
00:02:10,190 --> 00:02:12,290
be Josephus n minus one.

37
00:02:12,290 --> 00:02:12,650
Okay.

38
00:02:12,650 --> 00:02:14,450
So that's the smaller problem.

39
00:02:14,450 --> 00:02:19,610
So if we have this we have discussed that we just need to add k to this.

40
00:02:19,610 --> 00:02:28,550
And then we'll have to do modulo n okay n is the size of the problem at this particular instance.

41
00:02:28,550 --> 00:02:32,750
And this will give us the answer to the bigger problem okay.

42
00:02:32,750 --> 00:02:35,390
So we will go ahead and return this.

43
00:02:35,390 --> 00:02:37,490
So this is going to be the recursive case.

44
00:02:37,910 --> 00:02:39,560
And that's it okay.

45
00:02:39,560 --> 00:02:46,820
So notice we are using the solution to a smaller problem to arrive at the answer for a bigger problem.

46
00:02:46,820 --> 00:02:51,440
Now let's go ahead and run this code and see if it's passing all the test cases.

47
00:02:52,370 --> 00:02:55,490
And you can see that it's passing all the test cases.

48
00:02:55,490 --> 00:02:57,860
Now again do make use of the user logs.

49
00:02:57,860 --> 00:03:01,280
They will help you debug your code in case you are stuck somewhere.