1
00:00:00,340 --> 00:00:01,510
Welcome back.

2
00:00:01,510 --> 00:00:08,920
Now let's go ahead and take a look at how we can write the pseudo code for approach number two to solve

3
00:00:08,920 --> 00:00:10,420
the Josephus problem.

4
00:00:10,420 --> 00:00:14,980
We have already discussed the base case as well as the recursive case.

5
00:00:14,980 --> 00:00:16,900
So this should be a cakewalk.

6
00:00:16,900 --> 00:00:18,310
So let's take a look at it.

7
00:00:18,310 --> 00:00:19,930
So we write a function.

8
00:00:19,930 --> 00:00:21,430
Let's just call it winner.

9
00:00:21,430 --> 00:00:25,180
And we pass the parameters n and k to it.

10
00:00:25,180 --> 00:00:33,220
And again when we write the code over here we need to take care of the base case as well as the recursive

11
00:00:33,220 --> 00:00:33,790
case.

12
00:00:33,790 --> 00:00:41,470
And once we have written the function we will be calling it and whatever we get back from it.

13
00:00:41,470 --> 00:00:44,050
So return winner n comma k.

14
00:00:44,050 --> 00:00:49,600
So whatever we get back over here, we'll add one to it to make it one indexed.

15
00:00:49,600 --> 00:00:53,110
So we are writing the code for the zero indexed approach.

16
00:00:53,110 --> 00:00:56,920
So over here whatever we get back would be the index position.

17
00:00:56,920 --> 00:00:58,900
And then which is zero indexed.

18
00:00:58,900 --> 00:01:01,990
And we'll add one to it to make it one indexed.

19
00:01:01,990 --> 00:01:03,460
So let's get started.

20
00:01:03,910 --> 00:01:05,890
What would be the base condition.

21
00:01:05,890 --> 00:01:11,830
So the base condition as we've discussed is the case where only one person is left.

22
00:01:11,830 --> 00:01:16,990
So if there is just one person will return the index zero.

23
00:01:16,990 --> 00:01:19,210
And that that would be the base condition.

24
00:01:19,210 --> 00:01:19,480
Right.

25
00:01:19,480 --> 00:01:22,270
So if n is equal to one return zero.

26
00:01:22,270 --> 00:01:24,820
So over here that would give us zero.

27
00:01:25,000 --> 00:01:30,280
Let's imagine the case that we are just given the problem where n is equal to one and k is for example

28
00:01:30,280 --> 00:01:30,790
four.

29
00:01:30,790 --> 00:01:33,130
So there's just one person right.

30
00:01:33,130 --> 00:01:35,470
So the winner has to be that one person.

31
00:01:35,470 --> 00:01:38,740
So over here if n is equal to one we'll return zero.

32
00:01:38,740 --> 00:01:40,090
And that would be over here.

33
00:01:40,090 --> 00:01:41,200
We'll get zero over here.

34
00:01:41,200 --> 00:01:44,200
And we will add one to it to make it one indexed.

35
00:01:44,200 --> 00:01:45,850
So this is the base case.

36
00:01:45,850 --> 00:01:48,850
Now let's go ahead and write the recursive case.

37
00:01:49,330 --> 00:01:55,960
So if this is not the case then we'll have to find the winner for n minus one k.

38
00:01:55,960 --> 00:01:58,060
So this is the subproblem.

39
00:01:58,060 --> 00:02:05,140
And we have seen that to convert this to the position of the original problem or to use the solution

40
00:02:05,140 --> 00:02:10,780
to the sub problem to solve the original problem, we just need to add k to it.

41
00:02:10,780 --> 00:02:16,030
And then we have to take modulo n and n is for this particular instance right.

42
00:02:16,030 --> 00:02:19,210
So this is how we will be solving this question.

43
00:02:19,210 --> 00:02:21,130
And remember how this works out.

44
00:02:21,130 --> 00:02:22,240
So again that's it.

45
00:02:22,240 --> 00:02:24,370
So we have we are done with writing the pseudo code.

46
00:02:24,370 --> 00:02:31,420
And how this works is initially let's say we have n is equal to five and k is equal to three.

47
00:02:32,390 --> 00:02:35,810
So this will go ahead and call the winner.

48
00:02:35,810 --> 00:02:37,820
Function for n is equal to four.

49
00:02:37,850 --> 00:02:39,170
K is equal to three.

50
00:02:39,680 --> 00:02:42,170
This will go ahead and call the winner.

51
00:02:42,170 --> 00:02:44,780
Function for n is equal to three and k is equal to three.

52
00:02:44,810 --> 00:02:46,250
This will go ahead and call.

53
00:02:46,250 --> 00:02:50,810
The same function for n is equal to two and k is equal to three, and this will call.

54
00:02:50,810 --> 00:02:54,020
The function for n is equal to one and k is equal to three.

55
00:02:54,020 --> 00:02:57,620
So this over here will start to return right.

56
00:02:57,620 --> 00:03:04,160
So this will return zero and using zero this over here will find the value.

57
00:03:04,160 --> 00:03:06,350
And it will go on in in such a manner.

58
00:03:06,350 --> 00:03:08,420
So this will return then this will return.

59
00:03:08,420 --> 00:03:14,780
And finally we are using the solutions to the subproblems to solve the original problem.

60
00:03:14,780 --> 00:03:16,730
Let's quickly trace it out.

61
00:03:16,730 --> 00:03:19,340
So let's say n is equal to five.

62
00:03:19,430 --> 00:03:21,920
So we have 12345.

63
00:03:22,700 --> 00:03:24,860
And let's say k is equal to three.

64
00:03:25,760 --> 00:03:28,070
So initially the function calls.

65
00:03:28,070 --> 00:03:31,850
The Wiener function for n is equal to five and k is equal to three.

66
00:03:31,880 --> 00:03:34,190
This calls the same function recursively.

67
00:03:34,190 --> 00:03:35,990
For n is equal to four three.

68
00:03:36,290 --> 00:03:41,750
This goes to three, three, two, three and one comma three.

69
00:03:41,750 --> 00:03:43,190
So let's see how this works.

70
00:03:43,190 --> 00:03:46,400
And again we know that once we get the solution to the subproblem.

71
00:03:46,400 --> 00:03:48,290
So let's just call it subproblem.

72
00:03:48,290 --> 00:03:49,640
So this will be an index.

73
00:03:49,640 --> 00:03:53,270
We'll add k to it and we will do modulo.

74
00:03:54,640 --> 00:03:55,510
N okay.

75
00:03:55,510 --> 00:03:57,580
So n is for that particular instance.

76
00:03:57,580 --> 00:04:01,180
So this is how we have discussed the approach as well as the pseudocode.

77
00:04:01,180 --> 00:04:02,830
So again let's take a look at it.

78
00:04:02,830 --> 00:04:08,620
So over here when n is equal to one and k is equal to three this is gonna hit the base condition.

79
00:04:08,620 --> 00:04:11,080
And therefore this will return three.

80
00:04:11,440 --> 00:04:11,770
Sorry.

81
00:04:11,770 --> 00:04:13,240
This will return zero right.

82
00:04:13,240 --> 00:04:15,130
So this will return zero.

83
00:04:15,130 --> 00:04:22,570
So this is giving back zero and two comma three has the call to this one.

84
00:04:22,570 --> 00:04:23,830
And then to that.

85
00:04:23,830 --> 00:04:25,090
So this is zero right.

86
00:04:25,090 --> 00:04:28,540
To that we will be adding three which is k.

87
00:04:28,540 --> 00:04:31,060
And then we'll take percentage two.

88
00:04:31,060 --> 00:04:32,860
Because at this point n is two.

89
00:04:32,860 --> 00:04:37,180
So three percentage two is equal to one okay.

90
00:04:37,180 --> 00:04:40,030
So three modulo two is equal to one.

91
00:04:40,030 --> 00:04:42,940
So this is going to return the value one.

92
00:04:43,890 --> 00:04:44,490
Okay.

93
00:04:44,490 --> 00:04:49,500
And again in this call, in this call over here again we'll have the same thing where the sub problem

94
00:04:49,500 --> 00:04:50,490
was two comma three.

95
00:04:50,490 --> 00:04:52,020
So this is returning one.

96
00:04:52,020 --> 00:04:54,480
And we are adding k to it which is three.

97
00:04:54,480 --> 00:04:56,910
So this four four modulo.

98
00:04:56,910 --> 00:05:01,770
And the length over here is three four modulo three is equal to one.

99
00:05:02,340 --> 00:05:04,650
So this is going to return the value one.

100
00:05:05,190 --> 00:05:09,780
And in this call again we had the sub problem which is giving the value one.

101
00:05:09,780 --> 00:05:16,230
To that we are adding three and taking modulo four at this point, because n is equal to four, so four

102
00:05:16,230 --> 00:05:19,530
modulo four is equal to zero okay.

103
00:05:19,530 --> 00:05:21,240
So this is returning zero.

104
00:05:21,240 --> 00:05:26,910
And in this call we had the sub problem which is four comma three which returned zero.

105
00:05:26,910 --> 00:05:29,730
To that we are adding k which is three.

106
00:05:29,730 --> 00:05:36,600
And then we are taking modulo five because that's the value of n at this instance.

107
00:05:36,600 --> 00:05:40,290
So three modulo five is three itself.

108
00:05:40,290 --> 00:05:42,930
And this is the position okay.

109
00:05:42,930 --> 00:05:45,420
Which the function will return.

110
00:05:45,420 --> 00:05:51,540
And then as we've seen in the pseudo code we will add one to it to get the answer which is four.

111
00:05:51,540 --> 00:05:54,180
And again let's quickly take a dry run.

112
00:05:54,180 --> 00:06:00,780
And we have seen already that in the case of n is equal to five and k is equal to three, four is the

113
00:06:00,780 --> 00:06:01,680
safe position.

114
00:06:01,680 --> 00:06:03,090
But let's just quickly see it.

115
00:06:03,090 --> 00:06:06,510
So we start counting over here 123.

116
00:06:06,510 --> 00:06:09,150
This person is eliminated 123.

117
00:06:09,150 --> 00:06:11,730
This person is eliminated 123.

118
00:06:11,730 --> 00:06:14,160
This person is eliminated 123.

119
00:06:14,160 --> 00:06:15,630
This person is eliminated.

120
00:06:15,630 --> 00:06:18,720
And this is indeed the safe position.