1
00:00:00,390 --> 00:00:04,440
The Tower of Hanoi is a famous coding interview question.

2
00:00:04,440 --> 00:00:07,350
So let's go ahead and take a look at this question.

3
00:00:07,680 --> 00:00:09,600
So over here we have the question.

4
00:00:09,600 --> 00:00:10,890
Let's read it together.

5
00:00:11,160 --> 00:00:14,730
We have three roads and n disks.

6
00:00:15,690 --> 00:00:22,290
The objective of the puzzle is to move the entire stack to another rod.

7
00:00:22,500 --> 00:00:27,390
Initially, these disks are in the rod one.

8
00:00:27,390 --> 00:00:34,350
You need to print all the steps of disk movement so that all the disks reach the third rod.

9
00:00:34,650 --> 00:00:37,410
Also find and return the total moves.

10
00:00:37,410 --> 00:00:45,090
Note the disks are arranged such that the top disk is numbered one, and the bottom most disk is numbered

11
00:00:45,090 --> 00:00:45,660
n.

12
00:00:45,690 --> 00:00:55,320
Also, all the disks have different sizes, and a bigger disk cannot be put on the top of a smaller

13
00:00:55,320 --> 00:00:55,830
disk.

14
00:00:55,830 --> 00:00:58,770
You can only move one disk at a time.

15
00:00:58,770 --> 00:01:00,600
So this is the question at hand.

16
00:01:01,310 --> 00:01:07,190
Let's now first try to understand what is asked in the problem statement.

17
00:01:07,430 --> 00:01:11,450
So over here it's mentioned that we are given three rods.

18
00:01:11,480 --> 00:01:11,870
Okay.

19
00:01:11,870 --> 00:01:13,430
So we are given three rods.

20
00:01:13,430 --> 00:01:15,230
Let's draw the three rods over here.

21
00:01:15,230 --> 00:01:16,400
So this is rod one.

22
00:01:16,400 --> 00:01:19,280
This is rod two and this is rod three.

23
00:01:19,490 --> 00:01:26,930
And let's say for understanding this question let's assume that rod one has three disks.

24
00:01:26,930 --> 00:01:29,900
So these are three disks on rod one.

25
00:01:29,900 --> 00:01:33,080
Notice that the size of the disks are different.

26
00:01:33,080 --> 00:01:40,040
And it's also given that you cannot place a bigger disk on top of a smaller disk.

27
00:01:40,040 --> 00:01:42,080
So the note is the arrangement over here.

28
00:01:42,080 --> 00:01:52,190
And the question is we need to move all these disks over here from this rod over here to the final rod

29
00:01:52,190 --> 00:01:52,580
okay.

30
00:01:52,580 --> 00:01:55,730
So we need to move the entire stack to another rod.

31
00:01:55,730 --> 00:01:56,960
So this is the puzzle.

32
00:01:56,960 --> 00:02:00,890
But the condition is that we can only move one disk at a time.

33
00:02:00,890 --> 00:02:02,270
So that's mentioned over here.

34
00:02:02,270 --> 00:02:08,900
And a moment like this where you have a bigger disk on top of a smaller disk is wrong.

35
00:02:08,900 --> 00:02:10,490
So this is the question over here.

36
00:02:10,490 --> 00:02:16,640
And we can call these rods as the from rod the two rod.

37
00:02:16,640 --> 00:02:21,080
And this could be called the auxiliary rod or the helper rod.

38
00:02:21,140 --> 00:02:25,640
Now what is the expected output as per the question.

39
00:02:25,640 --> 00:02:28,670
There are two things that we need to take care.

40
00:02:28,670 --> 00:02:30,890
One is that we need to print.

41
00:02:30,890 --> 00:02:34,550
That's mentioned over here all the steps of disk movement.

42
00:02:34,550 --> 00:02:37,940
So we need to print all the steps of disk movement.

43
00:02:37,940 --> 00:02:42,230
And we also need to return the total number of moves.

44
00:02:42,230 --> 00:02:50,660
For example, if the question is that we have to move three disks from the from rod to the two rod,

45
00:02:50,660 --> 00:02:54,380
then the output that is expected is something like this.

46
00:02:54,380 --> 00:02:59,060
So for example, the first print statement over here says move disk one.

47
00:02:59,060 --> 00:03:00,950
So let's say this is disk one.

48
00:03:00,950 --> 00:03:02,030
This is disk two.

49
00:03:02,060 --> 00:03:03,440
This is disk three.

50
00:03:03,440 --> 00:03:07,550
So move disk one from rod one to rod three.

51
00:03:07,700 --> 00:03:11,540
So we have to move this guy from rod one to rod three.

52
00:03:11,540 --> 00:03:14,810
And then move disk two from rod one to row two.

53
00:03:14,810 --> 00:03:16,040
And it goes on like that okay.

54
00:03:16,040 --> 00:03:17,900
So we will see how we come up with this.

55
00:03:17,900 --> 00:03:21,110
But again over here we are just trying to understand the question.

56
00:03:21,110 --> 00:03:28,790
So we need to move all these disks from the from rod to the two rod without violating the given conditions,

57
00:03:28,790 --> 00:03:37,610
which is that we can only move one disk at a time, and we can never place a larger disk on top of a

58
00:03:37,700 --> 00:03:38,750
smaller disk.

59
00:03:38,750 --> 00:03:39,920
So this is a violation.

60
00:03:39,920 --> 00:03:40,490
Okay.

61
00:03:44,330 --> 00:03:45,440
So this is a violation.

62
00:03:45,440 --> 00:03:46,880
So this is the question at hand.

63
00:03:46,880 --> 00:03:49,070
And we need to print all the movements.

64
00:03:49,070 --> 00:03:54,650
And finally notice that we have seven print statements over here or seven movements of disks.

65
00:03:54,650 --> 00:03:58,280
And that's why we need to return the value seven as well.

66
00:03:58,280 --> 00:04:05,090
So we have understood the question in the next video, let's try to think about how we can solve this

67
00:04:05,090 --> 00:04:10,460
and what method would be an appropriate method for solving this question.