Welcome back.
So using approach number two we were able to achieve a better time complexity.
As you can see over here.
Approach number one had a time complexity of O of n squared.
But approach number two has a time complexity of O of n which is much better.
Now let's proceed and take a look at approach number three.
And in approach number three we will try to improve upon the space complexity by following the same
methodology that we used in approach number two, but then implement it in an iterative manner.
So let's get started.
Now to develop the intuition on how we can implement this in an iterative manner.
Let's take an example where n is equal to five and k is equal to three.
Now for this we just have to iterate from n is equal to two.
Up to n is equal to five, because we already know that if n is equal to one, the output is just going
to be equal to zero.
And again remember we are following the zero index method.
So this is the position zero.
And then we will just add one just like we did in the recursive solution.
So let's take a look at this and let's see how this works out.
So for n is equal to one we know that the position.
Which will have the winner is zero.
And again, this adding one will be taken care of at the end.
So let's work with this zero now.
Now over here, because n is equal to five we have to keep iterating till we reach five okay.
So the next value for n after one is going to be two.
So again notice over here we are iterating from 2 to 5.
Now when n is equal to two what would be the safe position.
Again the logic is the same.
We just have to add k to the position number.
So zero which is the position of the smaller problem or the sub problem.
So that was the safe position.
To that we are going to add the value of k which is three.
And then we are going to take modulo the value of n at that point.
Right.
So over here n is equal to two.
So that's why we're doing modulo two.
So this is the same approach that we followed and discussed in approach number two.
All right.
So three modulo two gives the answer as one.
And again this is the position one.
Now if we could stop at n is equal to two.
Or let's say the question itself was n is equal to two and k is equal to three.
We would have to add one.
So that's the same thing that we had over here okay.
So that's just to convert zero indexed to one indexed.
But let's say over here because the problem is that n is equal to five.
We don't need to do that.
We continue to n is equal to three.
Now again just a quick side note.
Is this correct.
Just let's quickly check it.
Let's say we just had two numbers one and two.
So if k is equal to three.
So the first person to move out would be 123.
So one would be eliminated.
And two is the answer.
And that's this two over here.
So it's working okay.
So just to check that now let's continue.
And let's keep iterating up till five.
So the next value n is equal to three.
So we take this value over here which is the safe position.
We add k to it which is three.
So one plus three.
And then we take modulo the value of n which is three.
So four modulo three gives us the value one because four divided by three has a remainder one.
Now if n was three, the safe position would be one.
Now let's proceed to n is equal to four.
Again, we take this position over here, we add k to it and take modulo the value of n at this point,
which is four.
So four modulo four is equal to zero because four divided by four gives a remainder zero.
So if n is equal to four, the safe position is zero.
Now let's proceed to n is equal to five.
We take the zero at k to it and take modulo the value of n, which is five.
So three modulo five gives us three.
So the position of the safe place is three which is zero indexed.
All right.
And then to convert it to one index we have to add one to it.
And that gives us the answer as four.
Now let's quickly check it out.
Like let's say if n is equal to five is this over here indeed the safe position.
So let's just quickly check.
So the first person to move out or lose would be 123.
So this guy is out.
The next person to move out would be 123 which is this position over here.
So this person is out and then we go on 123.
So person five is out.
And one, two three person two is out.
And you can see that indeed position four or this person over here is placed at the safe position.
And that's what we got over here.
So this is how we can implement the iterative approach.
Now, in the next video, let's go ahead and take a look at the complexity of this solution.