1
00:00:00,140 --> 00:00:07,520
In the previous video, we have discussed approach number one for solving the Josephus problem.

2
00:00:07,520 --> 00:00:12,830
Now let's go ahead and write the pseudocode of the approach that we have discussed.

3
00:00:12,830 --> 00:00:20,270
So the first step was that we will build an array that looks like one, two, three etc. up to n.

4
00:00:20,270 --> 00:00:22,310
So n is an input parameter.

5
00:00:22,310 --> 00:00:26,030
So based on that we will create this array over here.

6
00:00:26,030 --> 00:00:32,090
And after that let's say we have a function and we call that function winner.

7
00:00:32,090 --> 00:00:39,080
And to the function we pass the array and the start point where we have to start counting at every point.

8
00:00:39,080 --> 00:00:45,470
And the first call to this function would be that we pass this array over here, and we start counting

9
00:00:45,470 --> 00:00:49,010
at index zero, which is this position over here.

10
00:00:49,100 --> 00:00:53,240
Now inside the function we have to write the base case.

11
00:00:53,240 --> 00:00:54,800
And the recursive case.

12
00:00:54,800 --> 00:01:02,180
As we have discussed, the base case is that if you have just one person or one element remaining in

13
00:01:02,180 --> 00:01:06,260
the array, we just need to return that particular element, right.

14
00:01:06,260 --> 00:01:12,020
For example, let's say after some number of counts and let's say this was the initial array.

15
00:01:12,020 --> 00:01:19,190
And let's say after eliminating one person in each set, we keep doing that till one person only remains

16
00:01:19,190 --> 00:01:19,730
in the array.

17
00:01:19,730 --> 00:01:25,970
And if the array looks something like this, then the third position or this position over here is the

18
00:01:25,970 --> 00:01:26,420
winner.

19
00:01:26,420 --> 00:01:33,320
And that means we just have to return this value over here, which is at this point array of zero.

20
00:01:33,320 --> 00:01:35,270
So this is our base condition.

21
00:01:35,270 --> 00:01:39,500
And the recursive condition is that we just need to find.

22
00:01:39,500 --> 00:01:45,560
So if this is not true, if there are more than one elements in the array, then we just need to go

23
00:01:45,560 --> 00:01:50,870
ahead and identify this index over here, which is the index that we need to remove.

24
00:01:50,870 --> 00:01:51,200
Right.

25
00:01:51,200 --> 00:01:57,710
So the index to remove would be start plus k minus one which is what we have done over here.

26
00:01:57,710 --> 00:02:04,280
Start plus k minus one percentage the length of the array at that particular instance.

27
00:02:05,040 --> 00:02:05,610
All right.

28
00:02:05,610 --> 00:02:11,910
So once we have found this index, all we need to do is we just need to remove the element in the array

29
00:02:11,910 --> 00:02:13,080
at that index.

30
00:02:13,080 --> 00:02:20,730
And then we recursively call the same function passing the array which at this point has one element

31
00:02:20,790 --> 00:02:23,610
lesser compared to the previous instance of the array.

32
00:02:23,610 --> 00:02:27,870
And then we pass the index where they have to start counting.

33
00:02:27,870 --> 00:02:32,340
And we have seen that you can just pass this particular index itself, right.

34
00:02:32,340 --> 00:02:37,710
For example over here let's just quickly write that over here 12345.

35
00:02:37,710 --> 00:02:39,450
And this is index zero.

36
00:02:39,450 --> 00:02:40,320
This is index one.

37
00:02:40,320 --> 00:02:42,930
This is index two three and four.

38
00:02:42,930 --> 00:02:47,100
So over here we have seen that this was the first person to leave.

39
00:02:47,100 --> 00:02:48,540
So that's index one.

40
00:02:48,540 --> 00:02:51,180
So remove at this point would be index one.

41
00:02:51,180 --> 00:02:57,390
And after we remove this the array looks like this 134 and five.

42
00:02:57,390 --> 00:03:00,270
And we have to start counting over here.

43
00:03:00,270 --> 00:03:00,450
Right.

44
00:03:00,450 --> 00:03:02,250
So that's the rule of the game.

45
00:03:02,250 --> 00:03:03,900
So we start counting over here.

46
00:03:03,900 --> 00:03:10,830
And notice that this person is at index one at this point which was the index to be removed itself.

47
00:03:10,830 --> 00:03:11,100
Right.

48
00:03:11,100 --> 00:03:17,700
So that's why we can pass this index itself as the start value for the next set of counting.

49
00:03:17,700 --> 00:03:18,750
And that's it.

50
00:03:18,750 --> 00:03:23,910
We have written the pseudocode for approach one to solve the Josephus problem.