In the previous video, we have discussed approach number one for solving the Josephus problem.
Now let's go ahead and write the pseudocode of the approach that we have discussed.
So the first step was that we will build an array that looks like one, two, three etc. up to n.
So n is an input parameter.
So based on that we will create this array over here.
And after that let's say we have a function and we call that function winner.
And to the function we pass the array and the start point where we have to start counting at every point.
And the first call to this function would be that we pass this array over here, and we start counting
at index zero, which is this position over here.
Now inside the function we have to write the base case.
And the recursive case.
As we have discussed, the base case is that if you have just one person or one element remaining in
the array, we just need to return that particular element, right.
For example, let's say after some number of counts and let's say this was the initial array.
And let's say after eliminating one person in each set, we keep doing that till one person only remains
in the array.
And if the array looks something like this, then the third position or this position over here is the
winner.
And that means we just have to return this value over here, which is at this point array of zero.
So this is our base condition.
And the recursive condition is that we just need to find.
So if this is not true, if there are more than one elements in the array, then we just need to go
ahead and identify this index over here, which is the index that we need to remove.
Right.
So the index to remove would be start plus k minus one which is what we have done over here.
Start plus k minus one percentage the length of the array at that particular instance.
All right.
So once we have found this index, all we need to do is we just need to remove the element in the array
at that index.
And then we recursively call the same function passing the array which at this point has one element
lesser compared to the previous instance of the array.
And then we pass the index where they have to start counting.
And we have seen that you can just pass this particular index itself, right.
For example over here let's just quickly write that over here 12345.
And this is index zero.
This is index one.
This is index two three and four.
So over here we have seen that this was the first person to leave.
So that's index one.
So remove at this point would be index one.
And after we remove this the array looks like this 134 and five.
And we have to start counting over here.
Right.
So that's the rule of the game.
So we start counting over here.
And notice that this person is at index one at this point which was the index to be removed itself.
Right.
So that's why we can pass this index itself as the start value for the next set of counting.
And that's it.
We have written the pseudocode for approach one to solve the Josephus problem.