Tower of Hanoi Problem in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Tower of Hanoi problem?

To move all disks from the source peg to the destination peg following the rules: only one disk can be moved at a time, a larger disk cannot be placed on top of a smaller disk, and only the top disk of any peg can be moved.

beginner

What are the three pegs called in the Tower of Hanoi problem?

Source peg (where disks start), Auxiliary peg (used for temporary storage), and Destination peg (where disks need to be moved).

intermediate

How many moves are required to solve the Tower of Hanoi problem with n disks?

The minimum number of moves required is 2^n - 1, where n is the number of disks.

intermediate

Explain the recursive approach to solve the Tower of Hanoi problem.

Move n-1 disks from source to auxiliary peg, move the nth (largest) disk to destination peg, then move the n-1 disks from auxiliary to destination peg using source as auxiliary.

beginner

What is the base case in the recursive Tower of Hanoi solution?

When there is only one disk (n=1), simply move it from the source peg to the destination peg.

How many disks can be moved at a time in the Tower of Hanoi problem?

A Only one disk

B Two disks

C Any number of disks

D Three disks

Only one disk can be moved at a time according to the rules.

Which peg is used as temporary storage in the Tower of Hanoi problem?

A Destination peg

B Auxiliary peg

C Source peg

D None

The auxiliary peg is used as temporary storage to help move disks.

What is the minimum number of moves to solve Tower of Hanoi with 3 disks?

A 7

B 3

C 5

D 9

Minimum moves = 2^3 - 1 = 7.

In the recursive solution, what do you do after moving n-1 disks to the auxiliary peg?

A Move n-1 disks to destination peg

B Move all disks back to source peg

C Stop the process

D Move the largest disk to destination peg

After moving n-1 disks to auxiliary, move the largest disk to destination peg.

What is the base case for the Tower of Hanoi recursive function?

A When n = 2

B When n = 0

C When n = 1

D When n = 3

The base case is when there is only one disk (n=1).

Describe the steps to solve the Tower of Hanoi problem recursively for n disks.

Think about breaking the problem into smaller parts.

Explain why the minimum number of moves for Tower of Hanoi is 2^n - 1.

Consider how the moves add up with each disk.