Welcome back.
So we will be discussing three approaches of solving the Josephus problem.
And notice over here that the initial approach, which would be, I would say the most intuitive one,
has a time complexity of O of n square.
And we will see this later, and then we will see how we can improve this to a time complexity of O
of n.
Now, between the second and the third approach, you can see that it's the third approach has a better
space complexity.
And this is because we will convert approach two, which is a recursive solution to an iterative solution.
So let's get started with approach one.
Now first let's try to build an intuition on how we can solve this question.
Notice first that the problem itself is defined recursively.
Now what do I mean with that.
You can see that the way the game is designed, there is recursion inside the game.
Right.
So for example, let's say there are five people.
And let's say that k is equal to seven.
Now we would first go ahead and find the first person to eliminate which would be this person over here.
And then we would repeat this process again and again till we find the last person standing.
So the problem itself is defined recursively.
Another interesting thing that we can notice over here is that if k is equal to seven, notice that
the person over here eliminated is the second person okay.
And the length of this circle is five.
So this two over here is the same as seven modulo five which is two right.
So whenever you have something in a question which is of a circular nature, you can think it's a good
thing to think whether we could be using the modulo operator.
All right.
So again modulo means remainder after division.
So seven modulo five means if you divide seven by five what would be the remainder.
So seven is equal to one into five plus two.
So that's why seven modulo five gives you the remainder which is equal to two.
Now let's see whether we can use this thing that we have seen that we could use the modulo operator.
Let's see whether we can use this to solve this question by just using an array.
Now we could use circular data structures, but probably that's an overkill for this question.
Let's see whether we can just solve this question by using the modulo operator.
So again let's take a look at this example over here where we had five people standing in a circle.
Now if we were to use an array these are the five people in a straight line okay.
Now let's write the indices of this array.
Over here we have zero one, two, three and four.
And let's say we start over here.
All right.
So we start over here and let's say K again is seven.
So let's try to identify the first person who has to leave okay.
Or the first person who's losing in this game.
So for this we start with zero.
So that's zero over here.
And we're going to add to this seven minus one.
And then take modulo five.
Let's try to understand this.
And let's try to understand the reasoning behind this okay.
So zero plus seven would be seven.
So seven minus one is six.
And six modulo five is equal to one.
And that is this index over here.
Now if I were to count seven people that's 12345, six and seven.
Notice that I will be reaching over here.
And that is this index that we have got.
Now again, it should be pretty clear why we are adding seven.
So we are starting at index zero and we are adding seven.
But then why are we subtracting one from it.
That's because this over here the array over here is zero indexed right.
So that's why we have to subtract one.
And then we have to take modulo five because these people are standing in a circle.
Let's also quickly take the case where for example let's say k was equal to three.
Now again let's say we are starting at index zero itself.
Now if I add three to index zero zero plus three gives me three.
Right now let's count three people and just see where the first person who is moving out of the circle
is standing.
So that's one.
This is two and this is three.
Notice that it is at index two and not at index three.
That is why we have to subtract one from this, which is what we're doing over here because the array
is zero indexed.
So we are very clear with this part over here zero plus seven minus one.
Now let's think of why we are doing modulo five okay.
So zero plus seven minus one.
Again that's six.
And if we want to count to six over here again we are not using a circular data structure.
So there should be a way to come back to the beginning of the array after the end of the array.
And that is why we are taking the modulo operator.
And we have already seen that in action over here.
So six modulo five gives us one.
And that's this index over here.
And we have seen that this is the person that has to move out of the circle the first time.
All right.
So again we have seen that minus one is required because the array is zero indexed.
And we have seen that this is the first person who has to leave the circle or who is losing for the
first time.
And then we just have to keep doing this till only one person is left among the five people in this
particular example.
So let's take a look at that in a greater detail.
Let's make some space over here.
So if we want to code out this solution, that is we just need to always keep finding the person who
has to leave the index of that particular person.
And then let's say we just have to remove that person from the array.
And then we have to keep doing this again and again.
So we know that we are dealing with a recursive solution over here.
And when we want to build the recursive solution, there are just two cases that we need to think about.
First, the base case and secondly the recursive case.
Now we have already discussed the recursive case, which is what we have over here.
Because notice we find this index.
We remove that person and we keep doing this till one person alone is left.
So that's the recursive case.
Now the base case is when there is only one person left.
And in that case we just have to return that element right.
Again I'm saying element over here because we are going to create this array.
And let's say there is just one person left and let's say hypothetically that's this person over here.
So in that case the array would look like this.
And this would be the element at index zero.
So to return this we just have to return the value of the element which is the last element in the array.
Once we hit the base case in the next video, let's go ahead and write the pseudocode for this approach
that we have discussed.