1
00:00:00,080 --> 00:00:01,100
Welcome back.

2
00:00:01,100 --> 00:00:07,880
So using approach number two we were able to achieve a better time complexity.

3
00:00:07,880 --> 00:00:09,320
As you can see over here.

4
00:00:09,350 --> 00:00:14,210
Approach number one had a time complexity of O of n squared.

5
00:00:14,210 --> 00:00:20,000
But approach number two has a time complexity of O of n which is much better.

6
00:00:20,000 --> 00:00:23,720
Now let's proceed and take a look at approach number three.

7
00:00:23,720 --> 00:00:31,100
And in approach number three we will try to improve upon the space complexity by following the same

8
00:00:31,100 --> 00:00:37,520
methodology that we used in approach number two, but then implement it in an iterative manner.

9
00:00:37,790 --> 00:00:39,050
So let's get started.

10
00:00:40,040 --> 00:00:46,610
Now to develop the intuition on how we can implement this in an iterative manner.

11
00:00:46,610 --> 00:00:51,710
Let's take an example where n is equal to five and k is equal to three.

12
00:00:51,740 --> 00:00:56,630
Now for this we just have to iterate from n is equal to two.

13
00:00:56,630 --> 00:01:04,130
Up to n is equal to five, because we already know that if n is equal to one, the output is just going

14
00:01:04,130 --> 00:01:05,300
to be equal to zero.

15
00:01:05,300 --> 00:01:08,540
And again remember we are following the zero index method.

16
00:01:08,540 --> 00:01:10,250
So this is the position zero.

17
00:01:10,250 --> 00:01:14,870
And then we will just add one just like we did in the recursive solution.

18
00:01:14,870 --> 00:01:17,990
So let's take a look at this and let's see how this works out.

19
00:01:17,990 --> 00:01:21,320
So for n is equal to one we know that the position.

20
00:01:22,050 --> 00:01:25,260
Which will have the winner is zero.

21
00:01:25,260 --> 00:01:28,530
And again, this adding one will be taken care of at the end.

22
00:01:28,530 --> 00:01:30,450
So let's work with this zero now.

23
00:01:30,450 --> 00:01:38,490
Now over here, because n is equal to five we have to keep iterating till we reach five okay.

24
00:01:38,490 --> 00:01:42,540
So the next value for n after one is going to be two.

25
00:01:42,570 --> 00:01:45,960
So again notice over here we are iterating from 2 to 5.

26
00:01:45,960 --> 00:01:50,910
Now when n is equal to two what would be the safe position.

27
00:01:50,910 --> 00:01:53,580
Again the logic is the same.

28
00:01:53,580 --> 00:01:57,270
We just have to add k to the position number.

29
00:01:57,270 --> 00:02:01,860
So zero which is the position of the smaller problem or the sub problem.

30
00:02:01,860 --> 00:02:03,510
So that was the safe position.

31
00:02:03,510 --> 00:02:06,900
To that we are going to add the value of k which is three.

32
00:02:06,900 --> 00:02:11,490
And then we are going to take modulo the value of n at that point.

33
00:02:11,490 --> 00:02:11,700
Right.

34
00:02:11,700 --> 00:02:13,470
So over here n is equal to two.

35
00:02:13,500 --> 00:02:15,450
So that's why we're doing modulo two.

36
00:02:15,480 --> 00:02:20,880
So this is the same approach that we followed and discussed in approach number two.

37
00:02:20,880 --> 00:02:21,540
All right.

38
00:02:21,540 --> 00:02:25,530
So three modulo two gives the answer as one.

39
00:02:25,530 --> 00:02:27,900
And again this is the position one.

40
00:02:27,900 --> 00:02:30,780
Now if we could stop at n is equal to two.

41
00:02:30,780 --> 00:02:35,130
Or let's say the question itself was n is equal to two and k is equal to three.

42
00:02:35,130 --> 00:02:36,660
We would have to add one.

43
00:02:36,660 --> 00:02:39,660
So that's the same thing that we had over here okay.

44
00:02:39,660 --> 00:02:42,780
So that's just to convert zero indexed to one indexed.

45
00:02:42,780 --> 00:02:47,700
But let's say over here because the problem is that n is equal to five.

46
00:02:47,700 --> 00:02:48,960
We don't need to do that.

47
00:02:48,960 --> 00:02:51,360
We continue to n is equal to three.

48
00:02:51,360 --> 00:02:54,000
Now again just a quick side note.

49
00:02:54,000 --> 00:02:54,810
Is this correct.

50
00:02:54,810 --> 00:02:56,160
Just let's quickly check it.

51
00:02:56,160 --> 00:02:58,920
Let's say we just had two numbers one and two.

52
00:02:58,920 --> 00:03:00,720
So if k is equal to three.

53
00:03:00,720 --> 00:03:03,870
So the first person to move out would be 123.

54
00:03:03,870 --> 00:03:05,610
So one would be eliminated.

55
00:03:05,610 --> 00:03:06,870
And two is the answer.

56
00:03:06,870 --> 00:03:08,280
And that's this two over here.

57
00:03:08,280 --> 00:03:09,360
So it's working okay.

58
00:03:09,360 --> 00:03:12,270
So just to check that now let's continue.

59
00:03:12,270 --> 00:03:15,180
And let's keep iterating up till five.

60
00:03:15,180 --> 00:03:17,400
So the next value n is equal to three.

61
00:03:17,400 --> 00:03:20,970
So we take this value over here which is the safe position.

62
00:03:20,970 --> 00:03:23,430
We add k to it which is three.

63
00:03:23,430 --> 00:03:24,840
So one plus three.

64
00:03:24,840 --> 00:03:28,440
And then we take modulo the value of n which is three.

65
00:03:28,440 --> 00:03:34,650
So four modulo three gives us the value one because four divided by three has a remainder one.

66
00:03:34,650 --> 00:03:38,880
Now if n was three, the safe position would be one.

67
00:03:38,880 --> 00:03:41,280
Now let's proceed to n is equal to four.

68
00:03:42,060 --> 00:03:48,780
Again, we take this position over here, we add k to it and take modulo the value of n at this point,

69
00:03:48,780 --> 00:03:49,620
which is four.

70
00:03:49,620 --> 00:03:55,530
So four modulo four is equal to zero because four divided by four gives a remainder zero.

71
00:03:55,530 --> 00:03:59,070
So if n is equal to four, the safe position is zero.

72
00:03:59,070 --> 00:04:01,530
Now let's proceed to n is equal to five.

73
00:04:01,530 --> 00:04:07,020
We take the zero at k to it and take modulo the value of n, which is five.

74
00:04:07,020 --> 00:04:09,840
So three modulo five gives us three.

75
00:04:09,840 --> 00:04:15,990
So the position of the safe place is three which is zero indexed.

76
00:04:15,990 --> 00:04:16,620
All right.

77
00:04:16,620 --> 00:04:20,700
And then to convert it to one index we have to add one to it.

78
00:04:20,700 --> 00:04:23,100
And that gives us the answer as four.

79
00:04:23,100 --> 00:04:24,750
Now let's quickly check it out.

80
00:04:24,750 --> 00:04:29,880
Like let's say if n is equal to five is this over here indeed the safe position.

81
00:04:29,880 --> 00:04:31,200
So let's just quickly check.

82
00:04:31,200 --> 00:04:35,160
So the first person to move out or lose would be 123.

83
00:04:35,160 --> 00:04:36,690
So this guy is out.

84
00:04:36,690 --> 00:04:41,820
The next person to move out would be 123 which is this position over here.

85
00:04:41,820 --> 00:04:45,690
So this person is out and then we go on 123.

86
00:04:45,690 --> 00:04:47,400
So person five is out.

87
00:04:47,400 --> 00:04:50,040
And one, two three person two is out.

88
00:04:50,040 --> 00:04:56,790
And you can see that indeed position four or this person over here is placed at the safe position.

89
00:04:56,790 --> 00:04:58,770
And that's what we got over here.

90
00:04:58,770 --> 00:05:02,850
So this is how we can implement the iterative approach.

91
00:05:03,560 --> 00:05:08,300
Now, in the next video, let's go ahead and take a look at the complexity of this solution.