Tower of Hanoi Problem in DSA C++ - 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 rod to the destination rod 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

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

Source rod (where disks start), Auxiliary rod (used for temporary storage), and Destination rod (where disks must be moved).

intermediate

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

Move n-1 disks from source to auxiliary rod, move the largest disk to destination rod, then move n-1 disks from auxiliary to destination rod recursively.

beginner

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

The minimum number of moves is 2^n - 1.

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.

In the Tower of Hanoi problem, what is the role of the auxiliary rod?

A Starting point for disks

B Final destination for all disks

C Temporary storage to help move disks

D Rod that cannot be used

The auxiliary rod is used as temporary storage to help move disks between the source and destination rods.

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

A When there are no disks to move

B When there is only one disk to move

C When all disks are on the auxiliary rod

D When the destination rod is empty

The base case is when there is only one disk to move, which can be moved directly from source to destination.

How many moves are needed to solve Tower of Hanoi with 3 disks?

A 3

B 9

C 5

D 7

Minimum moves = 2^3 - 1 = 7.

Which of the following is NOT a rule of Tower of Hanoi?

A Disks can be stacked in any order on any rod

B A larger disk cannot be placed on a smaller disk

C Disks can be moved directly from source to destination or auxiliary

D Only one disk can be moved at a time

Disks must be stacked in order from largest at bottom to smallest at top; any order is not allowed.

What is the time complexity of the recursive Tower of Hanoi solution?

A O(2^n)

B O(n^2)

C O(n)

D O(log n)

The recursive solution has exponential time complexity O(2^n) because the number of moves doubles with each additional disk.

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

Think about breaking the problem into smaller subproblems.

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

Consider how moves increase as disks increase.

Practice

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

easy

A. 6

B. 5

C. 9

D. 7

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 D

4. Quick Check:

   2^3 - 1 = 7 [OK]

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

Common Mistakes:

• Using n instead of 2^n - 1
• Calculating 2*n - 1 instead of 2^n - 1
• Confusing number of disks with moves

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

easy

A. if (n == 1) move disk from source to destination;

B. if (n == 0) return;

C. if (n > 1) call recursive function;

D. if (n < 0) return;

Solution

1. Step 1: Identify the base case for recursion

   The base case is when there is only 1 disk to move, so move it directly.

2. Step 2: Check the options

   if (n == 1) move disk from source to destination; correctly states the base case: if (n == 1) move disk from source to destination.

3. Final Answer:

   if (n == 1) move disk from source to destination; -> Option A

4. Quick Check:

   Base case is n == 1 [OK]

Hint: Base case moves single disk directly [OK]

Common Mistakes:

• Using n == 0 as base case
• Not defining a base case
• Using incorrect condition like n < 0

3. What will be the output sequence of moves for Tower of Hanoi with 2 disks from peg A to peg C using peg B as auxiliary?

medium

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

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

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

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

Solution

1. Step 1: Understand the recursive move sequence for 2 disks

   Move top disk (1) from A to B, move bottom disk (2) from A to C, then move disk (1) from B to C.

2. Step 2: Match the sequence 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 correct sequence exactly.

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 B

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: For 2 disks: move top to aux, bottom to dest, top to dest [OK]

Common Mistakes:

• Swapping auxiliary and destination pegs
• Moving larger disk before smaller disk
• Incorrect move order

4. Identify the error in the following Tower of Hanoi recursive function snippet in C++:

void towerOfHanoi(int n, char source, char aux, char dest) {
  if (n == 1) {
    cout << "Move disk 1 from " << source << " to " << dest << endl;
    return;
  }
  towerOfHanoi(n - 1, source, dest, aux);
  cout << "Move disk " << n << " from " << source << " to " << dest << endl;
  towerOfHanoi(n - 1, aux, source, dest);
}

medium

A. The order of auxiliary and destination pegs is swapped in recursive calls.

B. Base case condition should be n == 0 instead of n == 1.

C. The function does not print the moves correctly.

D. The function lacks a return statement after recursive calls.

Solution

1. Step 1: Analyze recursive calls parameters

   The first recursive call should move n-1 disks from source to auxiliary using destination as auxiliary, so parameters should be (n-1, source, dest, aux).

2. Step 2: Identify incorrect parameter order

   In the code, the first call uses (n-1, source, aux, dest) which swaps aux and dest incorrectly.

3. Final Answer:

   The order of auxiliary and destination pegs is swapped in recursive calls. -> Option A

4. Quick Check:

   Correct peg order is crucial in recursion [OK]

Hint: Check peg order in recursive calls carefully [OK]

Common Mistakes:

• Swapping auxiliary and destination pegs
• Wrong base case condition
• Missing return statements

5. If the Tower of Hanoi problem is modified to have 4 pegs instead of 3, which of the following statements is true about the minimum number of moves required to move n disks?

hard

A. It remains the same as 3 pegs: 2^n - 1 moves.

B. It is always more than 2^n - 1 moves due to extra peg.

C. It is always less than 2^n - 1 moves but no exact formula is known.

D. It is exactly n^2 moves for any n.

Solution

1. Step 1: Understand the classic formula for 3 pegs

   For 3 pegs, minimum moves = 2^n - 1.

2. Step 2: Consider 4 pegs case

   With 4 pegs, the problem is more complex; fewer moves than 2^n - 1 are possible but no simple closed formula exists.

3. Final Answer:

   It is always less than 2^n - 1 moves but no exact formula is known. -> Option C

4. Quick Check:

   4 pegs reduce moves but formula unknown [OK]

Hint: More pegs reduce moves but no simple formula [OK]

Common Mistakes:

• Assuming formula 2^n - 1 applies to 4 pegs
• Thinking more pegs increase moves
• Assuming quadratic moves for 4 pegs