Tower of Hanoi Problem in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tower of Hanoi moves for 2 disks

What is the output of the following Tower of Hanoi Java code when called with 2 disks?

DSA Java

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

    public static void main(String[] args) {
        solve(2, 'A', 'C', 'B');
    }
}

A

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

B

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

C

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

D

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

💡 Hint

Remember the recursive steps: move n-1 disks to auxiliary, move largest disk, then move n-1 disks to target.

The Tower of Hanoi solution for 2 disks moves disk 1 from source to auxiliary, then disk 2 from source to target, then disk 1 from auxiliary to target.

🧠 Conceptual

intermediate

Number of moves required for Tower of Hanoi

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

A 8

B 16

C 15

D 31

💡 Hint

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

For 4 disks, minimum moves = 2^4 - 1 = 16 - 1 = 15.

🔧 Debug

advanced

Identify the error in Tower of Hanoi code

What error will the following Java Tower of Hanoi code produce when run with n=3? public static void solve(int n, char from, char to, char aux) { if (n == 0) { System.out.println("Move disk " + n + " from " + from + " to " + to); return; } solve(n - 1, from, aux, to); System.out.println("Move disk " + n + " from " + from + " to " + to); solve(n - 1, aux, to, from); }

A StackOverflowError due to infinite recursion

B Compilation error due to missing return type

C No output because base case never reached

D Prints moves including disk 0 which is invalid

💡 Hint

Check the base case condition and what it prints.

The base case triggers when n == 0 and prints a move for disk 0, which is invalid since disks start from 1.

🚀 Application

advanced

Trace Tower of Hanoi moves for 3 disks

What is the sequence of moves printed by the Tower of Hanoi algorithm for 3 disks moving from peg A to peg C using peg B as auxiliary?

A

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

B

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

C

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

D

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

💡 Hint

Follow the recursive pattern carefully: move n-1 disks to auxiliary, move largest disk, then move n-1 disks to target.

The correct sequence follows the standard recursive solution for 3 disks moving from A to C using B.

🧠 Conceptual

expert

Time complexity of Tower of Hanoi algorithm

What is the time complexity of the Tower of Hanoi recursive algorithm in terms of the number of disks n?

A O(n^2)

B O(2^n)

C O(n)

D O(n!)

💡 Hint

Each move doubles the previous moves plus one more move for the largest disk.

The recursive formula T(n) = 2*T(n-1) + 1 solves to O(2^n), exponential time complexity.

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