1
00:00:00,330 --> 00:00:02,520
Hey everyone and welcome back.

2
00:00:02,520 --> 00:00:08,340
Let's now do this interesting question which is called the Josephus problem.

3
00:00:08,340 --> 00:00:10,950
It's a very famous coding interview question.

4
00:00:10,950 --> 00:00:14,400
And there is an interesting story behind this question.

5
00:00:14,400 --> 00:00:19,290
This question is also called find the winner of the Circular Game.

6
00:00:20,350 --> 00:00:22,630
So the story goes like this.

7
00:00:22,630 --> 00:00:32,350
In 67 CE, Josephus and 40 fellow soldiers who were Jews, were surrounded by a group of Roman soldiers

8
00:00:32,350 --> 00:00:34,390
who were intent on capturing them.

9
00:00:34,390 --> 00:00:42,160
Okay, so the fellow soldiers who were with Josephus did not want to be captured, and they decided

10
00:00:42,160 --> 00:00:43,300
to kill themselves.

11
00:00:43,300 --> 00:00:47,350
But Josephus was not interested in committing suicide.

12
00:00:47,350 --> 00:00:53,020
So Josephus, who also was a mathematician, came up with a proposal.

13
00:00:53,020 --> 00:00:58,060
So there were a total of one plus 40 that is 41 soldiers.

14
00:00:58,060 --> 00:00:58,540
Right.

15
00:00:58,540 --> 00:01:02,440
So these 41 guys would stand in a circle.

16
00:01:04,050 --> 00:01:08,040
Okay, so imagine that you have 41 Jews over here.

17
00:01:08,040 --> 00:01:11,670
And then the they would start at this.

18
00:01:11,670 --> 00:01:13,920
So let's say this is the person at position one.

19
00:01:13,920 --> 00:01:15,630
This is the person at position two.

20
00:01:15,630 --> 00:01:16,890
And it goes on like that.

21
00:01:16,890 --> 00:01:21,480
So this is 3456, seven etc..

22
00:01:21,480 --> 00:01:28,350
And then the thing that they came up with and agreed to with each other was that the first person would

23
00:01:28,350 --> 00:01:29,430
kill this person.

24
00:01:29,430 --> 00:01:33,780
So this guy is killed, and then the next person, this guy would kill this person.

25
00:01:33,780 --> 00:01:36,090
So they would technically just keep counting.

26
00:01:36,090 --> 00:01:36,480
One, two.

27
00:01:36,510 --> 00:01:37,380
So one, two.

28
00:01:37,410 --> 00:01:38,490
This guy is killed.

29
00:01:38,490 --> 00:01:39,360
One, two.

30
00:01:39,360 --> 00:01:40,110
This guy is killed.

31
00:01:40,110 --> 00:01:40,710
One, two.

32
00:01:40,710 --> 00:01:41,550
This guy is killed.

33
00:01:41,550 --> 00:01:42,390
One, two.

34
00:01:42,420 --> 00:01:43,680
So eight would be killed.

35
00:01:43,680 --> 00:01:51,720
And then they would keep doing this till only one person was remaining and that person had to kill himself.

36
00:01:51,720 --> 00:01:53,940
So this is the plan that they came up with.

37
00:01:53,940 --> 00:02:02,640
So Joseph was proposed this, and he was standing strategically at the position where the last soldier

38
00:02:02,640 --> 00:02:07,110
would still keep standing, and that was at position 19.

39
00:02:07,110 --> 00:02:12,690
And then once all the others died, Josephus just surrendered to the Roman soldiers.

40
00:02:12,690 --> 00:02:15,060
So this is the story behind this game.

41
00:02:15,060 --> 00:02:20,100
Now, let's take a look at this question and let's try to understand this question together.

42
00:02:20,190 --> 00:02:23,250
There are n friends that are playing a game.

43
00:02:23,250 --> 00:02:29,700
The friends are sitting in a circle and are numbered from one to n in clockwise order.

44
00:02:29,730 --> 00:02:36,630
More formally, moving clockwise from the ith friend brings you to the I plus one friend for one less

45
00:02:36,630 --> 00:02:42,630
than equal to I, less than n, and moving clockwise from the nth friend brings you to the first friend.

46
00:02:42,630 --> 00:02:44,520
So basically they are in the in a circle.

47
00:02:44,820 --> 00:02:47,430
The rules of the game are as follows.

48
00:02:47,940 --> 00:02:52,380
Start at the first friend, count the next k friends.

49
00:02:52,380 --> 00:02:55,050
So in the story k was equal to two.

50
00:02:55,050 --> 00:02:59,250
But over here in this question k will be an input parameter.

51
00:02:59,430 --> 00:03:06,420
Count the next k friends in the clockwise direction, including the friend you started at.

52
00:03:06,990 --> 00:03:13,230
The counting wraps around the circle and may count some friends more than once.

53
00:03:13,230 --> 00:03:18,270
Okay, the last friend you counted leaves the circle and loses the game.

54
00:03:18,270 --> 00:03:23,730
If there is still more than one friend in the circle, go back to step two, starting from the friend

55
00:03:23,730 --> 00:03:27,900
immediately clockwise of the friend who just lost and repeat.

56
00:03:27,900 --> 00:03:32,610
So this is the same thing that we have seen in the story about Josephus.

57
00:03:32,610 --> 00:03:36,750
The only thing was k was equal to two in the case of Josephus.

58
00:03:37,170 --> 00:03:37,740
Okay.

59
00:03:37,740 --> 00:03:42,150
And then it says else the last friend in the circle wins the game.

60
00:03:42,150 --> 00:03:48,060
So in the case of Josephus and the 41, the total number of soldiers was 41.

61
00:03:48,060 --> 00:03:50,730
That position was position 19.

62
00:03:50,730 --> 00:03:55,050
Given the number of friends n, so n also was 41.

63
00:03:55,050 --> 00:03:56,370
In the case over here.

64
00:03:56,370 --> 00:04:03,120
But in this question, n would be an input parameter and an integer K returned the winner of the game.

65
00:04:03,120 --> 00:04:05,040
So this is the question at hand.

66
00:04:05,040 --> 00:04:09,990
For example, let's take n as four and k as two.

67
00:04:10,020 --> 00:04:11,730
Now who would be the winner?

68
00:04:11,730 --> 00:04:12,990
Let's try that okay.

69
00:04:12,990 --> 00:04:16,770
So we would have to seat these four people in a circle.

70
00:04:16,770 --> 00:04:18,600
So we have 1234.

71
00:04:18,600 --> 00:04:21,600
And we start at position one okay.

72
00:04:21,600 --> 00:04:23,880
And we count up to two.

73
00:04:23,910 --> 00:04:25,170
We count two right one two.

74
00:04:25,200 --> 00:04:27,450
So this is one and this is two okay.

75
00:04:27,450 --> 00:04:32,400
So the first friend to lose the game is the person who's standing over here.

76
00:04:32,400 --> 00:04:34,890
So one two this guy is eliminated.

77
00:04:34,890 --> 00:04:38,220
And then we are left with these three people.

78
00:04:38,220 --> 00:04:44,700
And we start to count with the next person which is this person over here.

79
00:04:44,700 --> 00:04:46,140
So that is what is mentioned over here.

80
00:04:46,140 --> 00:04:46,530
Right.

81
00:04:46,530 --> 00:04:51,120
So we start again over here and then we count one two.

82
00:04:51,120 --> 00:04:55,080
This person is eliminated and we are left with one and three.

83
00:04:55,200 --> 00:04:57,450
This why was this guy was eliminated.

84
00:04:57,450 --> 00:04:59,970
So the next person is person one.

85
00:04:59,970 --> 00:05:03,390
So we start with person one and one two.

86
00:05:03,390 --> 00:05:08,370
This person is eliminated and the winner is person one okay.

87
00:05:08,370 --> 00:05:09,990
And this should be our output.

88
00:05:09,990 --> 00:05:11,340
So this is the question.

89
00:05:11,340 --> 00:05:16,650
So we have seen an interesting story behind this question.

90
00:05:16,650 --> 00:05:19,290
And we have also understood this question.

91
00:05:19,290 --> 00:05:23,040
And we have clear with what the expected output is.

92
00:05:23,040 --> 00:05:26,310
Now let's go ahead and write a few test cases.

93
00:05:26,310 --> 00:05:33,690
If n is equal to one and k is equal to three, the output has to be one because there is just one person.

94
00:05:33,690 --> 00:05:33,990
Right.

95
00:05:33,990 --> 00:05:38,400
So again the question is about finding the last person standing.

96
00:05:38,400 --> 00:05:45,390
If n is equal to two and k is equal to three, notice that the output would be two because we start

97
00:05:45,390 --> 00:05:51,630
with one, one two, three and this guy is eliminated and the output would be two.

98
00:05:52,740 --> 00:05:55,830
Let's say n is equal to three and k is equal to three.

99
00:05:55,830 --> 00:05:59,130
In this case the winner, who would be the winner.

100
00:05:59,130 --> 00:06:00,600
Let's quickly trace it.

101
00:06:00,600 --> 00:06:02,010
So 123.

102
00:06:02,010 --> 00:06:03,600
This guy would be eliminated.

103
00:06:04,420 --> 00:06:07,090
And then we start with person one.

104
00:06:07,090 --> 00:06:08,500
So one two, three.

105
00:06:08,500 --> 00:06:13,990
So this guy would be eliminated and we are left with person two who is the winner okay.

106
00:06:13,990 --> 00:06:18,910
And if n is equal to four and let's say k is equal to three again let's find the winner.

107
00:06:18,910 --> 00:06:20,140
So 123.

108
00:06:20,140 --> 00:06:22,480
This guy gets eliminated 123.

109
00:06:22,480 --> 00:06:24,130
This guy gets eliminated.

110
00:06:24,130 --> 00:06:26,680
And then we have 123.

111
00:06:26,680 --> 00:06:28,240
This guy gets eliminated.

112
00:06:28,240 --> 00:06:30,910
And the winner is person one okay.

113
00:06:30,910 --> 00:06:33,490
Which is the output that is required.

114
00:06:33,490 --> 00:06:39,310
So we have understood the question and we have written down some test cases to think about the question

115
00:06:39,310 --> 00:06:40,270
in a better manner.

116
00:06:40,270 --> 00:06:45,700
In the next video, let's start thinking about how we can solve this question.