Hey everyone and welcome back.
So we are done with approach one for solving the Josephus problem.
Now let's proceed to approach number two.
So the question at hand is that we are given n comma k and we need to find the winner.
So that's very clear to us.
Now let's think about this scenario.
If you knew the winner for n minus one k.
Could you use this to find the winner for n comma k?
So in a way, we are thinking that if we knew the solution to the sub problem, which is n minus one
comma k, could we use it to solve the original problem which is n comma k.
Also notice that in the sub problem, k does not change because we know that k does not change in the
question, right?
Even when one person is eliminated, like one, two three, four, five.
Let's say it's we are always counting three.
Let's say k is equal to three.
So after one person is eliminated, that would be one, two, three.
After this person is eliminated, still k is three, right to find the next person.
So that would be one two, three.
So k does not change.
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
for n comma k?
All right.
So first let's build the intuition around this.
So for this let's use an example.
Let's say we have five people to start with.
So that's 12345.
And again let's take k to be equal to three.
Now let's go ahead and identify who the winner would be.
So we are starting to count at position one.
So the first person to go out would be the person over here.
Because 123 gives us three and this person is eliminated.
Then we start to count over here.
And again we count three one.
Two and three and this person is out and we start to count over here and let's count three.
So that's one, two and three.
And this person is out.
And we start to count again over here because that's the next guy.
So the next person to leave is one two and three.
So this person is eliminated.
And the safe position in this scenario is position number four or person number four.
Now n minus one.
So over here n was five.
So n minus one would be four.
So let's take a look at what is the safe position in this scenario where we have four people to start
with.
And let's keep k as three itself.
So again we start to count over here.
And the first person to be eliminated is position is person 3123.
The next person to be eliminated is 123.
So this person is eliminated again.
We start to count over here and the next person to be eliminated is one, two, three.
This guy is eliminated.
And we have found that the safe position is the position where person one was there.
All right.
So we have identified that in the case where n is equal to five and k is three, four is the safe position.
And in the case where n is equal to four and k is equal to three, one is the safe position.
Now let's try to think that if we knew this, that means if we knew that for n is equal to four and
k is equal to three, if we knew that one is the safe position, could we use this in some way to find
that four is the safe position for n is equal to five, and k is equal to three without actually having
to go through the way that we did it previously.
So let's think about this.
All right, so if I were to remove one person from these five people, and we have seen that the first
person to be removed is person three.
All right.
So if I were to remove this person I am left with four people over here.
Okay.
And over here I know that after I remove this person, I have to start to count over here.
Right?
So if I can write one over here and two over here and three over here and four over here now, because
I already know that one is the safe position in this scenario.
Therefore, the equivalent position of one over here is this person over here, which is four.
And therefore I would be able to use this result to identify that this is the safe position when there
are five people.
And again notice because over here we have we are starting over here and we have one less right.
So we would never reach this place in even if we don't eliminate it.
But again, let's quickly try to summarize what we have just seen.
So we knew that for n is equal to four and k is equal to three, one is the safe position and for n
is equal to five.
And k is equal to three.
To find the safe position, we just had to change the name of these places to their respective places
in this type of a scenario.
And then we could just directly say that over here we have one.
And over here we have four.
So therefore four would be the safe position for this scenario where n is equal to five and k is equal
to three.
So all we need to do is if we know the solution for n minus one k.
If we can convert that to its equivalent position in n comma k in the way that we've discussed over
here, we would be able to identify the safe position for n comma k.
Now how do we do that.
So let's write these four positions over here.
So that's 1234.
And notice that their equivalent positions over here are 451 and two.
So how do we convert 1 to 4 2 to 5 3 to 1 and 4 to 2.
For this let's use the value of k which is three in this case.
Notice that to convert 1 to 4 all I need to do is I need to add k to one.
So one plus three gives me four.
Similarly over here if I add k to 2 or 2 plus three gives me five.
Over here if I add three plus three that's equal to six.
But over here, because we are dealing with a circular scenario, we know that we have previously explored
that we could probably use the modulo operator.
And that's becoming handy over here because six modulo five notice gives us one which is what we want.
Similarly, four plus three gives us seven, and if you take modulo five on it, you get two, which
is what we want over here.
So this over here is actually how we will be able to solve the original problem using the solution to
the subproblem.
Or in other words this.
What we have seen over here is expressing how we can solve the original problem using the solution to
the subproblem, which is nothing but the recurrence relation, or it gives us the way that we can write
the recursive case in our code.
All right.
So notice all we did was we added k and then we take modulo the length of the solution of the original
problem.
So we have seen how the recurrence relation spans out and how we can use the solution to the subproblem
to solve the main solution.
And we have developed an intuition around this regarding why this works.
Now what would be the base condition for this?
The base condition notice would be just the case where you are left with only one element, right?
Again, let's say we start with n is equal to five and k is equal to three.
Now to find the solution for this we go to.
The subproblem n is equal to 4k is equal to three.
Again we go to n is equal to three, k is equal to three.
For finding the solution for this, and we keep doing this till n is equal to one and k is equal to
three.
Now if n is equal to one and k is equal to three, only one person is remaining and that particular
element or that particular person itself would give us the answer.
Right.
So we would just return index zero.
And then we will add one to it over here.
So this is the last valid case.
And in this case we will just return one.
Now you can write or approach this in two ways.
You can think of it by using zero index in a zero index manner or in a one index manner.
Now it's probably easier to code it out.
We'll see it when we take a look at the code.
If we take the zero index approach.
So all you can do is you can just return zero and then finally you just return zero plus one.
So this zero is what you get from here.
If there's just one person you just return index zero.
And then finally to convert it to the way that we count.
Right.
So let's imagine that you are just one person over here.
And you start with k is equal to three.
That one person itself is the winner.
Right.
So you just return the position of that one, the one person which is zero.
And then you add one to it to make it sound like we normally count.
So note is over here we have written 12345 not 01234.
So that's why we have to add this one over here.
So this should be very clear.
The base condition is that if there is just one person, that one person that the the one person who
is just there is the winner.
So that's the base condition.
And we have discussed the recurrence relation over here, which is to just add k and take modulo based
on the length of that problem.
All right.
In the next video let's go ahead and take a look at how we can write the pseudocode for this approach.