Tower of Hanoi Problem in DSA Javascript - 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, and a larger disk cannot be placed on top of a smaller disk.

beginner

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

What is the recursive approach to solve the Tower of Hanoi problem?

Move n-1 disks from source to auxiliary peg, move the nth disk to destination peg, then move n-1 disks from auxiliary to destination peg.

beginner

Why can't a larger disk be placed on top of a smaller disk in Tower of Hanoi?

Because it violates the problem's rules and makes the puzzle unsolvable; it ensures the order and challenge of the problem.

beginner

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

When there is only one disk, move it directly from the source peg to the destination peg.

How many pegs are used in the Tower of Hanoi problem?

A 3

B 2

C 4

D 1

The Tower of Hanoi problem uses exactly 3 pegs: source, auxiliary, and destination.

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

A 6

B 5

C 9

D 7

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 the nth disk to the destination peg

B Move n-1 disks to the source peg

C Move the nth disk to the auxiliary peg

D Stop the recursion

After moving n-1 disks to auxiliary, move the largest disk (nth) to destination.

Which of these is NOT a rule of Tower of Hanoi?

A Disks can be moved from any peg to any peg

B A larger disk cannot be placed on a smaller disk

C Disks can be stacked in any order

D Only one disk can be moved at a time

Disks must be stacked in order from largest at bottom to smallest at top.

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

A When there are no disks

B When there is one disk

C When all disks are on the auxiliary peg

D When all disks are on the destination peg

The base case is when there is only one disk to move directly.

Explain the recursive steps to solve the Tower of Hanoi problem with n disks.

Think about breaking the problem into smaller parts.

Describe the rules that must be followed when moving disks in the Tower of Hanoi problem.

Rules keep the puzzle challenging and solvable.

Practice

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

easy

A. 7

B. 6

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 A

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 - 1
• Confusing number of disks with moves

2. Which of the following is the correct base case condition in a recursive Tower of Hanoi function in JavaScript?

easy

A. if (n < 0) return;

B. if (n === 1) moveDisk();

C. if (n > 1) return;

D. if (n === 0) return;

Solution

1. Step 1: Identify base case for recursion

   The recursion stops when there are no disks to move, i.e., n === 0.

2. Step 2: Check the options

   if (n === 0) return; correctly returns when n is 0, stopping recursion.

3. Final Answer:

   if (n === 0) return; -> Option D

4. Quick Check:

   Base case is n === 0 [OK]

Hint: Base case stops recursion at zero disks [OK]

Common Mistakes:

• Using n === 1 as base case incorrectly
• Not stopping recursion causing infinite calls
• Using invalid conditions like n < 0

3. What will be the output sequence of moves for 2 disks in the Tower of Hanoi problem using this code snippet?

function towerOfHanoi(n, from, to, aux) {
  if (n === 0) 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 2 from A to C"
"Move disk 1 from B to A"
"Move disk 2 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 A to B"
"Move disk 2 from A to C"
"Move disk 1 from B to C"

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

Solution

1. Step 1: Trace recursive calls for n=2

   First move disk 1 from A to B, then disk 2 from A to C, then disk 1 from B to C.

2. Step 2: Match output with options

   "Move disk 1 from A to B" "Move disk 2 from A to C" "Move disk 1 from B to C" matches the exact sequence of moves printed by the code.

3. Final Answer:

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

4. Quick Check:

   Correct move sequence for 2 disks = "Move disk 1 from A to B" "Move disk 2 from A to C" "Move disk 1 from B to C" [OK]

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

Common Mistakes:

• Mixing source and auxiliary rods
• Confusing disk numbers in moves
• Ignoring order of recursive calls

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

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

medium

A. Swap 'to' and 'aux' in the first recursive call

B. Change base case to n === 0

C. Remove the second recursive call

D. Add an extra console.log before recursion

Solution

1. Step 1: Analyze recursive calls

   The first recursive call should move n-1 disks from 'from' to 'aux' using 'to' as auxiliary, but here 'to' and 'aux' are swapped.

2. Step 2: Correct the argument order

   Swapping 'to' and 'aux' in the first recursive call fixes the logic to move disks correctly.

3. Final Answer:

   Swap 'to' and 'aux' in the first recursive call -> Option A

4. Quick Check:

   Correct recursive call order fixes error [OK]

Hint: Check recursive call parameters carefully [OK]

Common Mistakes:

• Mixing auxiliary and target rods
• Incorrect base case causing infinite recursion
• Removing necessary recursive calls

5. You want to solve the Tower of Hanoi problem for 4 disks but only want to print moves where disk 1 is moved. How would you modify this function?

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

hard

A. Change base case to n === 1 and print only then

B. Add an if condition to print only when n === 1 inside the function

C. Remove recursive calls and print only disk 1 move

D. Print all moves but filter output outside the function

Solution

1. Step 1: Understand the requirement

   We want to print moves only when disk 1 moves, but still perform all recursive calls to solve the problem.

2. Step 2: Modify print statement with condition

   Add an if condition to print only when n === 1, so other moves are not printed but recursion continues.

3. Final Answer:

   Add an if condition to print only when n === 1 inside the function -> Option B

4. Quick Check:

   Conditional print inside recursion solves problem [OK]

Hint: Use if (n === 1) to print selectively [OK]

Common Mistakes:

• Changing base case breaks recursion
• Removing recursive calls stops solution
• Filtering output outside misses recursion logic