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.

Practice

1. What is the minimum number of moves required to solve the Tower of Hanoi problem with 3 disks?

easy

A. 6

B. 7

C. 8

D. 9

Solution

1. Step 1: Understand the formula for minimum moves

   The minimum moves required for n disks is 2^n - 1.

2. Step 2: Calculate for 3 disks

   For 3 disks, minimum moves = 2^3 - 1 = 8 - 1 = 7.

3. Final Answer:

   7 -> Option B

4. Quick Check:

   2^3 - 1 = 7 [OK]

Hint: Use formula 2^n - 1 for minimum moves [OK]

Common Mistakes:

• Forgetting to subtract 1
• Using n instead of 2^n
• Confusing moves with disks

2. Which of the following is the correct TypeScript function signature for solving Tower of Hanoi recursively?

easy

A. function towerOfHanoi(n: number, from: string, to: string, aux: string): void

B. function towerOfHanoi(n: string, from: number, to: number, aux: number): number

C. function towerOfHanoi(n: number, from: number, to: number): void

D. function towerOfHanoi(n: number): string

Solution

1. Step 1: Identify parameters needed for Tower of Hanoi

   We need number of disks (number), source peg (string), destination peg (string), and auxiliary peg (string).

2. Step 2: Match with function signature

   function towerOfHanoi(n: number, from: string, to: string, aux: string): void matches all parameters with correct types and returns void as it prints moves.

3. Final Answer:

   function towerOfHanoi(n: number, from: string, to: string, aux: string): void -> Option A

4. Quick Check:

   Correct parameters and return type [OK]

Hint: Check parameter types and count carefully [OK]

Common Mistakes:

• Using wrong parameter types
• Missing auxiliary peg parameter
• Wrong return type

3. What will be the output of the following TypeScript code snippet for Tower of Hanoi with 2 disks?

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}
towerOfHanoi(2, 'A', 'C', 'B');

medium

A. Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B

B. Move disk 2 from A to B
Move disk 1 from A to C
Move disk 2 from B to C

C. Move disk 1 from B to C
Move disk 2 from A to C
Move disk 1 from A to B

D. Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

Solution

1. Step 1: Trace first recursive call with n=2

   Call towerOfHanoi(1, 'A', 'B', 'C') prints "Move disk 1 from A to B".

2. Step 2: Print move for disk 2

   Prints "Move disk 2 from A to C".

3. Step 3: Trace second recursive call with n=1

   Call towerOfHanoi(1, 'B', 'C', 'A') prints "Move disk 1 from B to C".

4. Final Answer:

   Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C -> Option D

5. Quick Check:

   Follow recursion steps carefully [OK]

Hint: Follow recursion calls step-by-step [OK]

Common Mistakes:

• Mixing source and auxiliary pegs
• Printing moves in wrong order
• Confusing disk numbers

4. Identify the error in this Tower of Hanoi TypeScript function and select the fix:

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 0) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}

medium

A. Change base case to if (n === 1) and print move for disk 1

B. Change base case to if (n === 0) and remove print statement

C. Remove recursive calls and only print moves

D. Change print statement to print disk 0

Solution

1. Step 1: Analyze base case condition

   Base case should be when n equals 1, not 0, because disk numbering starts at 1.

2. Step 2: Fix base case and print statement

   Change if (n === 0) to if (n === 1) and print move for disk 1.

3. Final Answer:

   Change base case to if (n === 1) and print move for disk 1 -> Option A

4. Quick Check:

   Base case must handle smallest disk [OK]

Hint: Base case is n === 1, not zero [OK]

Common Mistakes:

• Using n === 0 as base case
• Printing move for disk 1 in wrong place
• Skipping base case

5. You want to solve Tower of Hanoi for 4 disks but only print moves where disk 1 is moved. Which modification to the recursive function is correct?

hard

A. Print all moves and filter disk 1 moves after recursion

B. Remove all recursive calls except for n=1

C. Add condition to print only if disk number is 1 inside the print statement

D. Change base case to n=2 and print only disk 1 moves

Solution

1. Step 1: Understand requirement to print only disk 1 moves

   We must keep recursion intact but print moves only when disk number is 1.

2. Step 2: Modify print statement with condition

   Add if (n === 1) before printing move to filter only disk 1 moves.

3. Final Answer:

   Add condition to print only if disk number is 1 inside the print statement -> Option C

4. Quick Check:

   Filter print, keep recursion [OK]

Hint: Use if condition inside print to filter moves [OK]

Common Mistakes:

• Removing recursive calls breaks solution
• Filtering moves after recursion wastes time
• Changing base case incorrectly