Tower of Hanoi Problem in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to print the move from source to destination.

DSA Java

System.out.println("Move disk from " + [1] + " to " + destination);

Drag options to blanks, or click blank then click option'

Asource

Btemp

Cdestination

Ddisk

Attempts:

3 left

💡 Hint

Common Mistakes

Using destination instead of source.

Using a variable that does not represent the peg.

The move is from the source peg to the destination peg, so we print the source variable.

2fill in blank

medium

Complete the code to call the Tower of Hanoi function recursively for n-1 disks.

DSA Java

towerOfHanoi([1] - 1, source, temp, destination);

Drag options to blanks, or click blank then click option'

An

B1

Csource

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of n-1.

Using peg names instead of number of disks.

We reduce the number of disks by 1 for the recursive call.

3fill in blank

hard

Fix the error in the base case condition to stop recursion when no disks are left.

DSA Java

if ([1] == 0) return;

Drag options to blanks, or click blank then click option'

Adestination

Bsource

Cn

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Checking peg names instead of disk count.

Using wrong variable in condition.

The base case checks if the number of disks n is zero to stop recursion.

4fill in blank

hard

Fill both blanks to correctly call the recursive steps before and after moving the largest disk.

DSA Java

towerOfHanoi([1] - 1, source, [2], destination);
// move disk
towerOfHanoi([1] - 1, [2], destination, source);

Drag options to blanks, or click blank then click option'

An

Btemp

Csource

Ddestination

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up peg names in recursive calls.

Using wrong variable for disk count.

We move n-1 disks using temp as auxiliary peg before and after moving the largest disk.

5fill in blank

hard

Fill all three blanks to complete the Tower of Hanoi method signature and recursive calls.

DSA Java

public static void towerOfHanoi(int [1], String [2], String [3], String destination) {
    if ([1] == 0) return;
    towerOfHanoi([1] - 1, [2], destination, [3]);
    System.out.println("Move disk from " + [2] + " to " + destination);
    towerOfHanoi([1] - 1, [3], [2], destination);
}

Drag options to blanks, or click blank then click option'

An

Bsource

Ctemp

Ddisk

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong parameter names.

Mixing peg names in recursive calls.

The method takes number of disks n, source peg, and temp peg as parameters. Recursive calls use these variables correctly.

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