Hey everyone and welcome back.
Let's now do this interesting question which is called the Josephus problem.
It's a very famous coding interview question.
And there is an interesting story behind this question.
This question is also called find the winner of the Circular Game.
So the story goes like this.
In 67 CE, Josephus and 40 fellow soldiers who were Jews, were surrounded by a group of Roman soldiers
who were intent on capturing them.
Okay, so the fellow soldiers who were with Josephus did not want to be captured, and they decided
to kill themselves.
But Josephus was not interested in committing suicide.
So Josephus, who also was a mathematician, came up with a proposal.
So there were a total of one plus 40 that is 41 soldiers.
Right.
So these 41 guys would stand in a circle.
Okay, so imagine that you have 41 Jews over here.
And then the they would start at this.
So let's say this is the person at position one.
This is the person at position two.
And it goes on like that.
So this is 3456, seven etc..
And then the thing that they came up with and agreed to with each other was that the first person would
kill this person.
So this guy is killed, and then the next person, this guy would kill this person.
So they would technically just keep counting.
One, two.
So one, two.
This guy is killed.
One, two.
This guy is killed.
One, two.
This guy is killed.
One, two.
So eight would be killed.
And then they would keep doing this till only one person was remaining and that person had to kill himself.
So this is the plan that they came up with.
So Joseph was proposed this, and he was standing strategically at the position where the last soldier
would still keep standing, and that was at position 19.
And then once all the others died, Josephus just surrendered to the Roman soldiers.
So this is the story behind this game.
Now, let's take a look at this question and let's try to understand this question together.
There are n friends that are playing a game.
The friends are sitting in a circle and are numbered from one to n in clockwise order.
More formally, moving clockwise from the ith friend brings you to the I plus one friend for one less
than equal to I, less than n, and moving clockwise from the nth friend brings you to the first friend.
So basically they are in the in a circle.
The rules of the game are as follows.
Start at the first friend, count the next k friends.
So in the story k was equal to two.
But over here in this question k will be an input parameter.
Count the next k friends in the clockwise direction, including the friend you started at.
The counting wraps around the circle and may count some friends more than once.
Okay, the last friend you counted leaves the circle and loses the game.
If there is still more than one friend in the circle, go back to step two, starting from the friend
immediately clockwise of the friend who just lost and repeat.
So this is the same thing that we have seen in the story about Josephus.
The only thing was k was equal to two in the case of Josephus.
Okay.
And then it says else the last friend in the circle wins the game.
So in the case of Josephus and the 41, the total number of soldiers was 41.
That position was position 19.
Given the number of friends n, so n also was 41.
In the case over here.
But in this question, n would be an input parameter and an integer K returned the winner of the game.
So this is the question at hand.
For example, let's take n as four and k as two.
Now who would be the winner?
Let's try that okay.
So we would have to seat these four people in a circle.
So we have 1234.
And we start at position one okay.
And we count up to two.
We count two right one two.
So this is one and this is two okay.
So the first friend to lose the game is the person who's standing over here.
So one two this guy is eliminated.
And then we are left with these three people.
And we start to count with the next person which is this person over here.
So that is what is mentioned over here.
Right.
So we start again over here and then we count one two.
This person is eliminated and we are left with one and three.
This why was this guy was eliminated.
So the next person is person one.
So we start with person one and one two.
This person is eliminated and the winner is person one okay.
And this should be our output.
So this is the question.
So we have seen an interesting story behind this question.
And we have also understood this question.
And we have clear with what the expected output is.
Now let's go ahead and write a few test cases.
If n is equal to one and k is equal to three, the output has to be one because there is just one person.
Right.
So again the question is about finding the last person standing.
If n is equal to two and k is equal to three, notice that the output would be two because we start
with one, one two, three and this guy is eliminated and the output would be two.
Let's say n is equal to three and k is equal to three.
In this case the winner, who would be the winner.
Let's quickly trace it.
So 123.
This guy would be eliminated.
And then we start with person one.
So one two, three.
So this guy would be eliminated and we are left with person two who is the winner okay.
And if n is equal to four and let's say k is equal to three again let's find the winner.
So 123.
This guy gets eliminated 123.
This guy gets eliminated.
And then we have 123.
This guy gets eliminated.
And the winner is person one okay.
Which is the output that is required.
So we have understood the question and we have written down some test cases to think about the question
in a better manner.
In the next video, let's start thinking about how we can solve this question.