1 00:00:00,110 --> 00:00:01,100 Welcome back. 2 00:00:01,100 --> 00:00:07,790 So we will be discussing three approaches of solving the Josephus problem. 3 00:00:07,790 --> 00:00:14,510 And notice over here that the initial approach, which would be, I would say the most intuitive one, 4 00:00:14,510 --> 00:00:17,870 has a time complexity of O of n square. 5 00:00:17,870 --> 00:00:23,870 And we will see this later, and then we will see how we can improve this to a time complexity of O 6 00:00:23,870 --> 00:00:24,560 of n. 7 00:00:24,560 --> 00:00:30,710 Now, between the second and the third approach, you can see that it's the third approach has a better 8 00:00:30,710 --> 00:00:32,000 space complexity. 9 00:00:32,000 --> 00:00:39,470 And this is because we will convert approach two, which is a recursive solution to an iterative solution. 10 00:00:40,530 --> 00:00:43,050 So let's get started with approach one. 11 00:00:43,080 --> 00:00:48,990 Now first let's try to build an intuition on how we can solve this question. 12 00:00:49,020 --> 00:00:54,900 Notice first that the problem itself is defined recursively. 13 00:00:54,930 --> 00:00:56,490 Now what do I mean with that. 14 00:00:56,490 --> 00:01:01,770 You can see that the way the game is designed, there is recursion inside the game. 15 00:01:01,770 --> 00:01:02,130 Right. 16 00:01:02,130 --> 00:01:05,130 So for example, let's say there are five people. 17 00:01:05,730 --> 00:01:08,310 And let's say that k is equal to seven. 18 00:01:08,310 --> 00:01:15,450 Now we would first go ahead and find the first person to eliminate which would be this person over here. 19 00:01:15,450 --> 00:01:23,070 And then we would repeat this process again and again till we find the last person standing. 20 00:01:23,070 --> 00:01:26,670 So the problem itself is defined recursively. 21 00:01:26,880 --> 00:01:34,170 Another interesting thing that we can notice over here is that if k is equal to seven, notice that 22 00:01:34,170 --> 00:01:38,940 the person over here eliminated is the second person okay. 23 00:01:38,940 --> 00:01:41,460 And the length of this circle is five. 24 00:01:41,460 --> 00:01:48,690 So this two over here is the same as seven modulo five which is two right. 25 00:01:48,690 --> 00:01:55,710 So whenever you have something in a question which is of a circular nature, you can think it's a good 26 00:01:55,710 --> 00:02:00,690 thing to think whether we could be using the modulo operator. 27 00:02:00,930 --> 00:02:01,500 All right. 28 00:02:01,500 --> 00:02:05,040 So again modulo means remainder after division. 29 00:02:05,040 --> 00:02:10,680 So seven modulo five means if you divide seven by five what would be the remainder. 30 00:02:10,680 --> 00:02:14,940 So seven is equal to one into five plus two. 31 00:02:14,940 --> 00:02:20,250 So that's why seven modulo five gives you the remainder which is equal to two. 32 00:02:20,280 --> 00:02:27,270 Now let's see whether we can use this thing that we have seen that we could use the modulo operator. 33 00:02:27,270 --> 00:02:34,980 Let's see whether we can use this to solve this question by just using an array. 34 00:02:34,980 --> 00:02:42,030 Now we could use circular data structures, but probably that's an overkill for this question. 35 00:02:42,030 --> 00:02:47,610 Let's see whether we can just solve this question by using the modulo operator. 36 00:02:47,610 --> 00:02:54,660 So again let's take a look at this example over here where we had five people standing in a circle. 37 00:02:54,660 --> 00:03:01,170 Now if we were to use an array these are the five people in a straight line okay. 38 00:03:01,170 --> 00:03:03,780 Now let's write the indices of this array. 39 00:03:03,780 --> 00:03:07,590 Over here we have zero one, two, three and four. 40 00:03:07,590 --> 00:03:10,080 And let's say we start over here. 41 00:03:11,180 --> 00:03:11,840 All right. 42 00:03:11,840 --> 00:03:16,610 So we start over here and let's say K again is seven. 43 00:03:16,610 --> 00:03:21,470 So let's try to identify the first person who has to leave okay. 44 00:03:21,470 --> 00:03:23,870 Or the first person who's losing in this game. 45 00:03:23,870 --> 00:03:26,660 So for this we start with zero. 46 00:03:26,660 --> 00:03:28,550 So that's zero over here. 47 00:03:28,550 --> 00:03:33,290 And we're going to add to this seven minus one. 48 00:03:33,290 --> 00:03:35,270 And then take modulo five. 49 00:03:35,270 --> 00:03:36,680 Let's try to understand this. 50 00:03:36,680 --> 00:03:39,740 And let's try to understand the reasoning behind this okay. 51 00:03:39,740 --> 00:03:43,100 So zero plus seven would be seven. 52 00:03:43,100 --> 00:03:46,130 So seven minus one is six. 53 00:03:46,130 --> 00:03:49,250 And six modulo five is equal to one. 54 00:03:49,250 --> 00:03:51,320 And that is this index over here. 55 00:03:51,320 --> 00:03:58,850 Now if I were to count seven people that's 12345, six and seven. 56 00:03:58,850 --> 00:04:01,280 Notice that I will be reaching over here. 57 00:04:01,280 --> 00:04:04,010 And that is this index that we have got. 58 00:04:04,010 --> 00:04:07,970 Now again, it should be pretty clear why we are adding seven. 59 00:04:07,970 --> 00:04:11,480 So we are starting at index zero and we are adding seven. 60 00:04:11,480 --> 00:04:15,020 But then why are we subtracting one from it. 61 00:04:15,020 --> 00:04:20,540 That's because this over here the array over here is zero indexed right. 62 00:04:20,540 --> 00:04:22,640 So that's why we have to subtract one. 63 00:04:22,640 --> 00:04:29,210 And then we have to take modulo five because these people are standing in a circle. 64 00:04:29,210 --> 00:04:35,810 Let's also quickly take the case where for example let's say k was equal to three. 65 00:04:36,020 --> 00:04:39,380 Now again let's say we are starting at index zero itself. 66 00:04:39,380 --> 00:04:45,050 Now if I add three to index zero zero plus three gives me three. 67 00:04:45,050 --> 00:04:52,400 Right now let's count three people and just see where the first person who is moving out of the circle 68 00:04:52,400 --> 00:04:53,000 is standing. 69 00:04:53,000 --> 00:04:53,840 So that's one. 70 00:04:53,840 --> 00:04:55,790 This is two and this is three. 71 00:04:55,790 --> 00:05:00,140 Notice that it is at index two and not at index three. 72 00:05:00,140 --> 00:05:06,650 That is why we have to subtract one from this, which is what we're doing over here because the array 73 00:05:06,650 --> 00:05:08,210 is zero indexed. 74 00:05:08,210 --> 00:05:13,730 So we are very clear with this part over here zero plus seven minus one. 75 00:05:15,080 --> 00:05:18,530 Now let's think of why we are doing modulo five okay. 76 00:05:18,530 --> 00:05:20,540 So zero plus seven minus one. 77 00:05:20,540 --> 00:05:21,800 Again that's six. 78 00:05:21,800 --> 00:05:27,980 And if we want to count to six over here again we are not using a circular data structure. 79 00:05:27,980 --> 00:05:33,830 So there should be a way to come back to the beginning of the array after the end of the array. 80 00:05:33,830 --> 00:05:37,040 And that is why we are taking the modulo operator. 81 00:05:37,040 --> 00:05:39,830 And we have already seen that in action over here. 82 00:05:39,830 --> 00:05:42,530 So six modulo five gives us one. 83 00:05:42,530 --> 00:05:44,420 And that's this index over here. 84 00:05:44,420 --> 00:05:49,520 And we have seen that this is the person that has to move out of the circle the first time. 85 00:05:49,520 --> 00:05:50,060 All right. 86 00:05:50,060 --> 00:05:54,650 So again we have seen that minus one is required because the array is zero indexed. 87 00:05:54,650 --> 00:06:00,530 And we have seen that this is the first person who has to leave the circle or who is losing for the 88 00:06:00,530 --> 00:06:01,130 first time. 89 00:06:01,130 --> 00:06:11,180 And then we just have to keep doing this till only one person is left among the five people in this 90 00:06:11,180 --> 00:06:12,530 particular example. 91 00:06:12,530 --> 00:06:16,040 So let's take a look at that in a greater detail. 92 00:06:16,040 --> 00:06:17,690 Let's make some space over here. 93 00:06:18,440 --> 00:06:25,640 So if we want to code out this solution, that is we just need to always keep finding the person who 94 00:06:25,640 --> 00:06:28,250 has to leave the index of that particular person. 95 00:06:28,250 --> 00:06:31,910 And then let's say we just have to remove that person from the array. 96 00:06:31,910 --> 00:06:34,730 And then we have to keep doing this again and again. 97 00:06:34,730 --> 00:06:39,410 So we know that we are dealing with a recursive solution over here. 98 00:06:39,410 --> 00:06:46,730 And when we want to build the recursive solution, there are just two cases that we need to think about. 99 00:06:46,730 --> 00:06:51,650 First, the base case and secondly the recursive case. 100 00:06:51,650 --> 00:06:57,230 Now we have already discussed the recursive case, which is what we have over here. 101 00:06:57,230 --> 00:06:59,840 Because notice we find this index. 102 00:06:59,840 --> 00:07:06,170 We remove that person and we keep doing this till one person alone is left. 103 00:07:06,170 --> 00:07:08,060 So that's the recursive case. 104 00:07:08,060 --> 00:07:12,530 Now the base case is when there is only one person left. 105 00:07:12,530 --> 00:07:18,410 And in that case we just have to return that element right. 106 00:07:18,920 --> 00:07:22,940 Again I'm saying element over here because we are going to create this array. 107 00:07:22,940 --> 00:07:29,240 And let's say there is just one person left and let's say hypothetically that's this person over here. 108 00:07:29,240 --> 00:07:32,180 So in that case the array would look like this. 109 00:07:32,180 --> 00:07:35,360 And this would be the element at index zero. 110 00:07:35,360 --> 00:07:43,850 So to return this we just have to return the value of the element which is the last element in the array. 111 00:07:43,850 --> 00:07:51,380 Once we hit the base case in the next video, let's go ahead and write the pseudocode for this approach 112 00:07:51,380 --> 00:07:52,670 that we have discussed.