Tower of Hanoi Problem in DSA Java - 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

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 must be moved).

intermediate

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

Move n-1 disks from source to auxiliary peg, move the largest disk to destination peg, then move n-1 disks from auxiliary to destination peg. Repeat this recursively until all disks are moved.

intermediate

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

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

beginner

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

Because the rules of the problem restrict placing a larger disk on a smaller one to maintain the order and avoid invalid moves.

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

A 1

B 2

C 3

D 4

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

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 peg

D When the largest disk is moved

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

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

A n + 1

B n^2

C n!

D 2^n - 1

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

In Tower of Hanoi, which peg is used as temporary storage during the moves?

A Auxiliary peg

B Source peg

C Destination peg

D None

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

Can you move more than one disk at a time in Tower of Hanoi?

A No, only one disk at a time

B Yes, if disks are on the same peg

C Yes, if disks are smaller

D Only if the disks are the same size

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

Describe the recursive steps to solve the Tower of Hanoi problem 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 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. 9

B. 6

C. 8

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 a recursive Tower of Hanoi function in Java?

easy

A. if (n < 0) return;

B. if (n == 1) return;

C. if (n == 0) return;

D. if (n > 1) return;

Solution

1. Step 1: Identify base case for recursion

   Base case stops recursion when no disks are left to move, i.e., n == 0.

2. Step 2: Check each option

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

3. Final Answer:

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

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 which causes extra calls
• Using negative values as base case
• Returning when n > 1 which stops too early

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

medium

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

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

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

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

Solution

1. Step 1: Understand move sequence for 2 disks

   Move smaller disk 1 from source A to auxiliary B.

2. Step 2: Move larger disk 2 from source A to destination C, then move disk 1 from B to C

   This completes the transfer following rules.

3. Final Answer:

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

4. Quick Check:

   Correct move order for 2 disks [OK]

Hint: Move smaller disk first to auxiliary, then largest to destination [OK]

Common Mistakes:

• Swapping disk numbers in moves
• Moving larger disk before smaller disk
• Incorrect order of moves

4. Identify the error in this Tower of Hanoi recursive function snippet:

void towerOfHanoi(int n, char from, char to, char aux) {
  if (n == 1) {
    System.out.println("Move disk 1 from " + from + " to " + to);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  System.out.println("Move disk " + n + " from " + from + " to " + to);
  towerOfHanoi(n - 1, aux, to, from);
}

medium

A. Base case should be if (n == 0) instead of if (n == 1)

B. There is no error; the function is correct

C. The print statement should be before the first recursive call

D. The order of parameters in recursive calls is incorrect

Solution

1. Step 1: Analyze base case correctness

   Base case n == 1 means move the single disk directly, which is correct.

2. Step 2: Check recursive calls and print order

   First move n-1 disks from source to auxiliary, then move nth disk, then move n-1 disks from auxiliary to destination. This matches the Tower of Hanoi logic.

3. Final Answer:

   There is no error; the function is correct -> Option B

4. Quick Check:

   Function matches Tower of Hanoi recursion [OK]

Hint: Check base case and recursive call order carefully [OK]

Common Mistakes:

• Changing base case to n == 0 causing infinite recursion
• Swapping parameters in recursive calls
• Moving print statement incorrectly

5. If the Tower of Hanoi problem has 4 disks, what is the total number of moves and what is the move sequence for the first two moves from source A to destination C using auxiliary B?

hard

A. Total moves: 15\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C

B. Total moves: 14\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from B to C

C. Total moves: 16\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C

D. Total moves: 15\nFirst move: Move disk 1 from A to C\nSecond move: Move disk 2 from A to B

Solution

1. Step 1: Calculate total moves for 4 disks

   Total moves = 2^4 - 1 = 16 - 1 = 15 moves.

2. Step 2: Determine first two moves in sequence

   First move: Move smallest disk 1 from A to B (auxiliary). Second move: Move disk 2 from A to C (destination).

3. Final Answer:

   Total moves: 15\nFirst move: Move disk 1 from A to B\nSecond move: Move disk 2 from A to C -> Option A

4. Quick Check:

   2^4 - 1 = 15 and correct first moves [OK]

Hint: Use formula for moves and remember smallest disk moves first [OK]

Common Mistakes:

• Incorrect total moves calculation
• Swapping first two moves
• Confusing auxiliary and destination rods