1 00:00:00,520 --> 00:00:01,780 Welcome back. 2 00:00:01,780 --> 00:00:06,760 So far we have understood what the question asks us to achieve. 3 00:00:06,760 --> 00:00:12,520 We have understood the Tower of Hanoi problem, and we have also understood that we can use recursion 4 00:00:12,520 --> 00:00:13,960 to solve this question. 5 00:00:14,470 --> 00:00:21,790 In this video, let's first develop an intuition regarding the approach that can be taken to solve this 6 00:00:21,790 --> 00:00:22,480 question. 7 00:00:22,720 --> 00:00:25,840 For this, let's take four cases. 8 00:00:26,050 --> 00:00:29,110 The case where there is just one disk given to us. 9 00:00:29,110 --> 00:00:34,990 If there are two disks given to us, three disks given to us, and then we'll generalize what we learn 10 00:00:34,990 --> 00:00:40,870 from these three scenarios and apply it to the general case where n disks are given to us. 11 00:00:40,870 --> 00:00:43,630 So let's start with the first case. 12 00:00:44,230 --> 00:00:46,750 Let's say we are just given one disk. 13 00:00:46,750 --> 00:00:48,850 So the problem would look like this. 14 00:00:48,850 --> 00:00:53,050 We have to move this disk from round one to round three. 15 00:00:53,050 --> 00:00:56,200 And this is pretty straightforward and easy. 16 00:00:56,200 --> 00:00:59,500 We can just move it from rod one to rod three right. 17 00:00:59,500 --> 00:01:00,610 So this is straightforward. 18 00:01:00,820 --> 00:01:05,200 Now what about the scenario where we have two disks. 19 00:01:05,200 --> 00:01:06,790 So it would look like this. 20 00:01:06,790 --> 00:01:08,470 Again we have three rods. 21 00:01:08,470 --> 00:01:11,110 And the two disks are over here. 22 00:01:11,620 --> 00:01:19,690 Now the intuitive approach of solving this would be we would move this particular disk over here to 23 00:01:19,690 --> 00:01:20,830 rod two. 24 00:01:20,950 --> 00:01:26,080 And then we would move this disk the orange disk to rod three. 25 00:01:26,080 --> 00:01:31,300 And then we can just move this disk over here on top of the orange one. 26 00:01:31,300 --> 00:01:34,210 And we would have solved the question right. 27 00:01:34,210 --> 00:01:40,690 So again this also is pretty straightforward because we are just dealing with two disks and it's pretty 28 00:01:40,690 --> 00:01:41,440 intuitive. 29 00:01:41,470 --> 00:01:43,840 Now an interesting observation over here. 30 00:01:43,840 --> 00:01:49,300 Notice that we did not move this particular disk over here directly to rod number three. 31 00:01:49,300 --> 00:01:53,740 Because if we did that then we would have this rod over here. 32 00:01:53,740 --> 00:01:59,200 And then the orange one cannot be placed on top of it, because it would violate the condition that 33 00:01:59,200 --> 00:02:02,680 a bigger disk cannot be on top of a smaller disk. 34 00:02:02,680 --> 00:02:09,040 So the approach that we have taken is first, we move the smaller disk to the helper or auxiliary rod. 35 00:02:09,040 --> 00:02:17,170 And then once we have the larger disk at the desired position, we move the smaller disk on top of it. 36 00:02:17,650 --> 00:02:21,490 Now let's proceed to the case where we have three disks. 37 00:02:21,490 --> 00:02:24,460 Now this case over here is interesting. 38 00:02:25,290 --> 00:02:27,180 How would we solve this? 39 00:02:27,510 --> 00:02:30,570 The approach that we could take is that we. 40 00:02:31,610 --> 00:02:37,970 Would have to first solve the case where we just have two disks, which is something we already know 41 00:02:37,970 --> 00:02:38,900 and remember. 42 00:02:38,900 --> 00:02:46,880 We discussed that we cannot move the smaller disks directly to the desired destination, because if 43 00:02:46,880 --> 00:02:52,610 we do that, then we would have to place this one, the orange one on top of it, right? 44 00:02:52,610 --> 00:02:53,600 It would look like this. 45 00:02:53,600 --> 00:02:58,400 And then the next move would be placing the orange disk on top of these. 46 00:02:58,400 --> 00:03:00,410 But this is a violation of the condition. 47 00:03:00,410 --> 00:03:02,360 So we cannot do this. 48 00:03:02,360 --> 00:03:10,190 But rather than that what we can do is first move these two disks to road number two. 49 00:03:10,640 --> 00:03:13,520 Once we have achieved that it would look like this. 50 00:03:13,520 --> 00:03:17,810 And remember, this step over here is a recursive step, right? 51 00:03:17,810 --> 00:03:22,850 Because we already know how to do this because we have discussed the case where we had two disks. 52 00:03:22,850 --> 00:03:24,950 So over here we have three disks. 53 00:03:24,950 --> 00:03:29,330 So we are aware of how to solve the scenario where we have two disks. 54 00:03:29,330 --> 00:03:35,750 And we're just going to use that to move these two disks from road one to rod two. 55 00:03:35,750 --> 00:03:37,220 So it would look like this. 56 00:03:37,220 --> 00:03:44,570 Once we have achieved this, we would just move this disk over here from rod one to rod three and it 57 00:03:44,570 --> 00:03:45,530 would look like this. 58 00:03:45,530 --> 00:03:52,700 And then again we would have a recursive call to move these two disks from rod two to rod three. 59 00:03:53,330 --> 00:03:57,920 So this is how we would solve the case where we have three disks. 60 00:03:57,920 --> 00:04:05,180 Now let's use what we have learned over here and apply it to the general case where we have n disks. 61 00:04:05,180 --> 00:04:07,760 So let's say we have n disks over here. 62 00:04:07,760 --> 00:04:11,240 The sub problem would be having n minus one disks. 63 00:04:11,240 --> 00:04:19,070 And we just have to move these n minus one disks recursively from rod one to round two. 64 00:04:19,070 --> 00:04:20,870 And it would look like this. 65 00:04:20,870 --> 00:04:28,790 So once we have achieved that we can move the largest disk over here from rod one to rod three. 66 00:04:28,790 --> 00:04:30,170 So that would look like this. 67 00:04:30,170 --> 00:04:31,460 Once we have achieved that. 68 00:04:32,360 --> 00:04:34,160 So we have the biggest one over here. 69 00:04:34,160 --> 00:04:43,790 And then all we need to do is again, recursively move these n minus one disks from rod to to rod three. 70 00:04:43,790 --> 00:04:45,320 So they would be on top. 71 00:04:45,320 --> 00:04:49,640 So these n minus one disks would be on top of the biggest disk. 72 00:04:49,640 --> 00:04:53,960 And we would have solved the question without violating any condition. 73 00:04:53,960 --> 00:04:58,040 So this is the approach that we will take to solve this question. 74 00:04:58,600 --> 00:05:04,720 So let's quickly summarize what we have learned over here about the approach, the base case, or the 75 00:05:04,720 --> 00:05:07,360 simplest or the last valid case. 76 00:05:07,360 --> 00:05:11,530 If there is just one disc and we have seen that, that's pretty straightforward. 77 00:05:11,530 --> 00:05:14,200 Just move the disk from rod one to rod three. 78 00:05:14,200 --> 00:05:19,540 And then we have also discussed the recursive case over here which involves three steps. 79 00:05:19,540 --> 00:05:25,570 So the first step is to move n minus one disks from rod one to rod two. 80 00:05:25,570 --> 00:05:30,700 Notice this is not the final destination rod, but it's the helper or auxiliary rod. 81 00:05:30,700 --> 00:05:33,760 So this is the first step in the recursive case. 82 00:05:33,760 --> 00:05:37,240 And then we have to move the nth disc. 83 00:05:38,370 --> 00:05:40,290 From round one to round three. 84 00:05:40,290 --> 00:05:48,390 And then finally again, we have to move these n minus one disks from the auxiliary or helper rod to 85 00:05:48,390 --> 00:05:49,830 the destination rod. 86 00:05:49,830 --> 00:05:52,350 So this is how we can solve this question. 87 00:05:52,350 --> 00:05:56,520 In the next video let's draw out the recursion tree. 88 00:05:57,060 --> 00:06:04,170 And that will make it very easy to proceed and code out the solution, as well as analyze the time and 89 00:06:04,170 --> 00:06:07,800 space complexity of the approach that we have come up with.