Welcome back.
Now let's go ahead and take a look at how we can write the pseudo code for approach number two to solve
the Josephus problem.
We have already discussed the base case as well as the recursive case.
So this should be a cakewalk.
So let's take a look at it.
So we write a function.
Let's just call it winner.
And we pass the parameters n and k to it.
And again when we write the code over here we need to take care of the base case as well as the recursive
case.
And once we have written the function we will be calling it and whatever we get back from it.
So return winner n comma k.
So whatever we get back over here, we'll add one to it to make it one indexed.
So we are writing the code for the zero indexed approach.
So over here whatever we get back would be the index position.
And then which is zero indexed.
And we'll add one to it to make it one indexed.
So let's get started.
What would be the base condition.
So the base condition as we've discussed is the case where only one person is left.
So if there is just one person will return the index zero.
And that that would be the base condition.
Right.
So if n is equal to one return zero.
So over here that would give us zero.
Let's imagine the case that we are just given the problem where n is equal to one and k is for example
four.
So there's just one person right.
So the winner has to be that one person.
So over here if n is equal to one we'll return zero.
And that would be over here.
We'll get zero over here.
And we will add one to it to make it one indexed.
So this is the base case.
Now let's go ahead and write the recursive case.
So if this is not the case then we'll have to find the winner for n minus one k.
So this is the subproblem.
And we have seen that to convert this to the position of the original problem or to use the solution
to the sub problem to solve the original problem, we just need to add k to it.
And then we have to take modulo n and n is for this particular instance right.
So this is how we will be solving this question.
And remember how this works out.
So again that's it.
So we have we are done with writing the pseudo code.
And how this works is initially let's say we have n is equal to five and k is equal to three.
So this will go ahead and call the winner.
Function for n is equal to four.
K is equal to three.
This will go ahead and call the winner.
Function for n is equal to three and k is equal to three.
This will go ahead and call.
The same function for n is equal to two and k is equal to three, and this will call.
The function for n is equal to one and k is equal to three.
So this over here will start to return right.
So this will return zero and using zero this over here will find the value.
And it will go on in in such a manner.
So this will return then this will return.
And finally we are using the solutions to the subproblems to solve the original problem.
Let's quickly trace it out.
So let's say n is equal to five.
So we have 12345.
And let's say k is equal to three.
So initially the function calls.
The Wiener function for n is equal to five and k is equal to three.
This calls the same function recursively.
For n is equal to four three.
This goes to three, three, two, three and one comma three.
So let's see how this works.
And again we know that once we get the solution to the subproblem.
So let's just call it subproblem.
So this will be an index.
We'll add k to it and we will do modulo.
N okay.
So n is for that particular instance.
So this is how we have discussed the approach as well as the pseudocode.
So again let's take a look at it.
So over here when n is equal to one and k is equal to three this is gonna hit the base condition.
And therefore this will return three.
Sorry.
This will return zero right.
So this will return zero.
So this is giving back zero and two comma three has the call to this one.
And then to that.
So this is zero right.
To that we will be adding three which is k.
And then we'll take percentage two.
Because at this point n is two.
So three percentage two is equal to one okay.
So three modulo two is equal to one.
So this is going to return the value one.
Okay.
And again in this call, in this call over here again we'll have the same thing where the sub problem
was two comma three.
So this is returning one.
And we are adding k to it which is three.
So this four four modulo.
And the length over here is three four modulo three is equal to one.
So this is going to return the value one.
And in this call again we had the sub problem which is giving the value one.
To that we are adding three and taking modulo four at this point, because n is equal to four, so four
modulo four is equal to zero okay.
So this is returning zero.
And in this call we had the sub problem which is four comma three which returned zero.
To that we are adding k which is three.
And then we are taking modulo five because that's the value of n at this instance.
So three modulo five is three itself.
And this is the position okay.
Which the function will return.
And then as we've seen in the pseudo code we will add one to it to get the answer which is four.
And again let's quickly take a dry run.
And we have seen already that in the case of n is equal to five and k is equal to three, four is the
safe position.
But let's just quickly see it.
So we start counting over here 123.
This person is eliminated 123.
This person is eliminated.
And this is indeed the safe position.