1
00:00:00,110 --> 00:00:01,940
Hey everyone and welcome back.

2
00:00:01,940 --> 00:00:06,710
So we are done with approach one for solving the Josephus problem.

3
00:00:06,710 --> 00:00:09,770
Now let's proceed to approach number two.

4
00:00:09,800 --> 00:00:17,480
So the question at hand is that we are given n comma k and we need to find the winner.

5
00:00:17,480 --> 00:00:19,220
So that's very clear to us.

6
00:00:19,220 --> 00:00:22,910
Now let's think about this scenario.

7
00:00:22,910 --> 00:00:27,500
If you knew the winner for n minus one k.

8
00:00:28,270 --> 00:00:33,160
Could you use this to find the winner for n comma k?

9
00:00:33,430 --> 00:00:41,170
So in a way, we are thinking that if we knew the solution to the sub problem, which is n minus one

10
00:00:41,170 --> 00:00:46,810
comma k, could we use it to solve the original problem which is n comma k.

11
00:00:46,840 --> 00:00:53,710
Also notice that in the sub problem, k does not change because we know that k does not change in the

12
00:00:53,710 --> 00:00:54,520
question, right?

13
00:00:54,520 --> 00:00:58,180
Even when one person is eliminated, like one, two three, four, five.

14
00:00:58,180 --> 00:01:00,370
Let's say it's we are always counting three.

15
00:01:00,370 --> 00:01:01,960
Let's say k is equal to three.

16
00:01:01,960 --> 00:01:05,710
So after one person is eliminated, that would be one, two, three.

17
00:01:05,710 --> 00:01:10,690
After this person is eliminated, still k is three, right to find the next person.

18
00:01:10,690 --> 00:01:12,550
So that would be one two, three.

19
00:01:12,610 --> 00:01:14,410
So k does not change.

20
00:01:14,410 --> 00:01:22,030
But let's think if we knew the answer to n minus one k, could we use it in some way to find the answer

21
00:01:22,030 --> 00:01:23,260
for n comma k?

22
00:01:24,420 --> 00:01:25,020
All right.

23
00:01:25,020 --> 00:01:28,470
So first let's build the intuition around this.

24
00:01:28,470 --> 00:01:30,840
So for this let's use an example.

25
00:01:30,840 --> 00:01:34,110
Let's say we have five people to start with.

26
00:01:34,110 --> 00:01:35,970
So that's 12345.

27
00:01:35,970 --> 00:01:39,390
And again let's take k to be equal to three.

28
00:01:39,420 --> 00:01:42,570
Now let's go ahead and identify who the winner would be.

29
00:01:42,570 --> 00:01:45,090
So we are starting to count at position one.

30
00:01:45,090 --> 00:01:49,050
So the first person to go out would be the person over here.

31
00:01:49,050 --> 00:01:53,970
Because 123 gives us three and this person is eliminated.

32
00:01:53,970 --> 00:01:56,340
Then we start to count over here.

33
00:01:56,340 --> 00:01:58,830
And again we count three one.

34
00:01:59,580 --> 00:02:05,670
Two and three and this person is out and we start to count over here and let's count three.

35
00:02:05,670 --> 00:02:07,980
So that's one, two and three.

36
00:02:07,980 --> 00:02:09,300
And this person is out.

37
00:02:09,300 --> 00:02:12,960
And we start to count again over here because that's the next guy.

38
00:02:12,960 --> 00:02:16,890
So the next person to leave is one two and three.

39
00:02:16,890 --> 00:02:18,600
So this person is eliminated.

40
00:02:18,600 --> 00:02:25,170
And the safe position in this scenario is position number four or person number four.

41
00:02:25,170 --> 00:02:27,180
Now n minus one.

42
00:02:27,180 --> 00:02:28,680
So over here n was five.

43
00:02:28,680 --> 00:02:30,870
So n minus one would be four.

44
00:02:30,870 --> 00:02:37,440
So let's take a look at what is the safe position in this scenario where we have four people to start

45
00:02:37,440 --> 00:02:37,770
with.

46
00:02:37,770 --> 00:02:40,680
And let's keep k as three itself.

47
00:02:40,680 --> 00:02:43,020
So again we start to count over here.

48
00:02:43,620 --> 00:02:49,260
And the first person to be eliminated is position is person 3123.

49
00:02:49,260 --> 00:02:52,620
The next person to be eliminated is 123.

50
00:02:52,620 --> 00:02:54,690
So this person is eliminated again.

51
00:02:54,690 --> 00:02:59,370
We start to count over here and the next person to be eliminated is one, two, three.

52
00:02:59,370 --> 00:03:00,600
This guy is eliminated.

53
00:03:00,600 --> 00:03:07,620
And we have found that the safe position is the position where person one was there.

54
00:03:07,620 --> 00:03:08,310
All right.

55
00:03:08,310 --> 00:03:15,690
So we have identified that in the case where n is equal to five and k is three, four is the safe position.

56
00:03:15,690 --> 00:03:22,290
And in the case where n is equal to four and k is equal to three, one is the safe position.

57
00:03:22,290 --> 00:03:31,200
Now let's try to think that if we knew this, that means if we knew that for n is equal to four and

58
00:03:31,200 --> 00:03:38,430
k is equal to three, if we knew that one is the safe position, could we use this in some way to find

59
00:03:38,430 --> 00:03:45,090
that four is the safe position for n is equal to five, and k is equal to three without actually having

60
00:03:45,090 --> 00:03:48,060
to go through the way that we did it previously.

61
00:03:48,060 --> 00:03:49,530
So let's think about this.

62
00:03:50,740 --> 00:03:57,130
All right, so if I were to remove one person from these five people, and we have seen that the first

63
00:03:57,130 --> 00:03:59,470
person to be removed is person three.

64
00:03:59,470 --> 00:03:59,890
All right.

65
00:03:59,890 --> 00:04:04,300
So if I were to remove this person I am left with four people over here.

66
00:04:04,300 --> 00:04:04,840
Okay.

67
00:04:04,840 --> 00:04:10,930
And over here I know that after I remove this person, I have to start to count over here.

68
00:04:10,930 --> 00:04:11,260
Right?

69
00:04:11,260 --> 00:04:18,760
So if I can write one over here and two over here and three over here and four over here now, because

70
00:04:18,760 --> 00:04:23,260
I already know that one is the safe position in this scenario.

71
00:04:23,260 --> 00:04:29,350
Therefore, the equivalent position of one over here is this person over here, which is four.

72
00:04:29,350 --> 00:04:37,060
And therefore I would be able to use this result to identify that this is the safe position when there

73
00:04:37,060 --> 00:04:38,320
are five people.

74
00:04:38,320 --> 00:04:45,160
And again notice because over here we have we are starting over here and we have one less right.

75
00:04:45,160 --> 00:04:48,760
So we would never reach this place in even if we don't eliminate it.

76
00:04:48,760 --> 00:04:52,810
But again, let's quickly try to summarize what we have just seen.

77
00:04:52,810 --> 00:05:00,220
So we knew that for n is equal to four and k is equal to three, one is the safe position and for n

78
00:05:00,220 --> 00:05:01,870
is equal to five.

79
00:05:03,040 --> 00:05:04,780
And k is equal to three.

80
00:05:04,810 --> 00:05:14,500
To find the safe position, we just had to change the name of these places to their respective places

81
00:05:14,500 --> 00:05:16,450
in this type of a scenario.

82
00:05:16,450 --> 00:05:20,350
And then we could just directly say that over here we have one.

83
00:05:20,350 --> 00:05:21,730
And over here we have four.

84
00:05:21,730 --> 00:05:28,060
So therefore four would be the safe position for this scenario where n is equal to five and k is equal

85
00:05:28,060 --> 00:05:28,570
to three.

86
00:05:28,810 --> 00:05:33,430
So all we need to do is if we know the solution for n minus one k.

87
00:05:35,640 --> 00:05:43,260
If we can convert that to its equivalent position in n comma k in the way that we've discussed over

88
00:05:43,260 --> 00:05:48,210
here, we would be able to identify the safe position for n comma k.

89
00:05:48,300 --> 00:05:49,770
Now how do we do that.

90
00:05:49,800 --> 00:05:52,110
So let's write these four positions over here.

91
00:05:52,110 --> 00:05:53,850
So that's 1234.

92
00:05:53,850 --> 00:06:00,210
And notice that their equivalent positions over here are 451 and two.

93
00:06:01,710 --> 00:06:06,840
So how do we convert 1 to 4 2 to 5 3 to 1 and 4 to 2.

94
00:06:07,170 --> 00:06:11,490
For this let's use the value of k which is three in this case.

95
00:06:11,520 --> 00:06:17,280
Notice that to convert 1 to 4 all I need to do is I need to add k to one.

96
00:06:17,280 --> 00:06:19,170
So one plus three gives me four.

97
00:06:19,200 --> 00:06:24,720
Similarly over here if I add k to 2 or 2 plus three gives me five.

98
00:06:24,750 --> 00:06:28,890
Over here if I add three plus three that's equal to six.

99
00:06:28,890 --> 00:06:34,560
But over here, because we are dealing with a circular scenario, we know that we have previously explored

100
00:06:34,560 --> 00:06:37,530
that we could probably use the modulo operator.

101
00:06:37,530 --> 00:06:44,610
And that's becoming handy over here because six modulo five notice gives us one which is what we want.

102
00:06:45,230 --> 00:06:52,280
Similarly, four plus three gives us seven, and if you take modulo five on it, you get two, which

103
00:06:52,280 --> 00:06:53,960
is what we want over here.

104
00:06:54,410 --> 00:07:03,440
So this over here is actually how we will be able to solve the original problem using the solution to

105
00:07:03,440 --> 00:07:04,580
the subproblem.

106
00:07:04,580 --> 00:07:06,710
Or in other words this.

107
00:07:06,710 --> 00:07:13,820
What we have seen over here is expressing how we can solve the original problem using the solution to

108
00:07:13,820 --> 00:07:20,810
the subproblem, which is nothing but the recurrence relation, or it gives us the way that we can write

109
00:07:20,810 --> 00:07:23,600
the recursive case in our code.

110
00:07:23,600 --> 00:07:24,140
All right.

111
00:07:24,140 --> 00:07:31,910
So notice all we did was we added k and then we take modulo the length of the solution of the original

112
00:07:31,910 --> 00:07:32,540
problem.

113
00:07:32,690 --> 00:07:39,680
So we have seen how the recurrence relation spans out and how we can use the solution to the subproblem

114
00:07:39,680 --> 00:07:42,350
to solve the main solution.

115
00:07:42,350 --> 00:07:46,610
And we have developed an intuition around this regarding why this works.

116
00:07:46,610 --> 00:07:49,670
Now what would be the base condition for this?

117
00:07:50,120 --> 00:07:57,410
The base condition notice would be just the case where you are left with only one element, right?

118
00:07:57,410 --> 00:08:01,280
Again, let's say we start with n is equal to five and k is equal to three.

119
00:08:01,430 --> 00:08:04,520
Now to find the solution for this we go to.

120
00:08:04,520 --> 00:08:07,520
The subproblem n is equal to 4k is equal to three.

121
00:08:07,520 --> 00:08:10,460
Again we go to n is equal to three, k is equal to three.

122
00:08:10,460 --> 00:08:16,760
For finding the solution for this, and we keep doing this till n is equal to one and k is equal to

123
00:08:16,760 --> 00:08:17,210
three.

124
00:08:17,240 --> 00:08:24,140
Now if n is equal to one and k is equal to three, only one person is remaining and that particular

125
00:08:24,140 --> 00:08:27,500
element or that particular person itself would give us the answer.

126
00:08:27,500 --> 00:08:27,680
Right.

127
00:08:27,680 --> 00:08:30,440
So we would just return index zero.

128
00:08:30,440 --> 00:08:32,210
And then we will add one to it over here.

129
00:08:32,210 --> 00:08:34,850
So this is the last valid case.

130
00:08:34,850 --> 00:08:38,060
And in this case we will just return one.

131
00:08:38,840 --> 00:08:41,990
Now you can write or approach this in two ways.

132
00:08:41,990 --> 00:08:48,590
You can think of it by using zero index in a zero index manner or in a one index manner.

133
00:08:48,590 --> 00:08:51,590
Now it's probably easier to code it out.

134
00:08:51,590 --> 00:08:53,570
We'll see it when we take a look at the code.

135
00:08:53,570 --> 00:08:55,850
If we take the zero index approach.

136
00:08:55,850 --> 00:09:01,910
So all you can do is you can just return zero and then finally you just return zero plus one.

137
00:09:01,910 --> 00:09:04,070
So this zero is what you get from here.

138
00:09:04,070 --> 00:09:07,580
If there's just one person you just return index zero.

139
00:09:07,580 --> 00:09:10,490
And then finally to convert it to the way that we count.

140
00:09:10,490 --> 00:09:10,670
Right.

141
00:09:10,670 --> 00:09:13,160
So let's imagine that you are just one person over here.

142
00:09:13,160 --> 00:09:15,170
And you start with k is equal to three.

143
00:09:15,170 --> 00:09:17,120
That one person itself is the winner.

144
00:09:17,120 --> 00:09:17,420
Right.

145
00:09:17,420 --> 00:09:22,100
So you just return the position of that one, the one person which is zero.

146
00:09:22,100 --> 00:09:26,810
And then you add one to it to make it sound like we normally count.

147
00:09:26,810 --> 00:09:32,000
So note is over here we have written 12345 not 01234.

148
00:09:32,000 --> 00:09:34,610
So that's why we have to add this one over here.

149
00:09:34,610 --> 00:09:36,980
So this should be very clear.

150
00:09:36,980 --> 00:09:43,370
The base condition is that if there is just one person, that one person that the the one person who

151
00:09:43,370 --> 00:09:45,320
is just there is the winner.

152
00:09:45,320 --> 00:09:47,240
So that's the base condition.

153
00:09:47,240 --> 00:09:53,600
And we have discussed the recurrence relation over here, which is to just add k and take modulo based

154
00:09:53,600 --> 00:09:56,000
on the length of that problem.

155
00:09:56,000 --> 00:09:56,840
All right.

156
00:09:57,410 --> 00:10:03,710
In the next video let's go ahead and take a look at how we can write the pseudocode for this approach.