Tower of Hanoi Problem in DSA C++ - 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 function call for 2 disks?

DSA C++

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        std::cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << std::endl;
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    std::cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << std::endl;
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    towerOfHanoi(2, 'A', 'C', 'B');
    return 0;
}

A

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

B

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

C

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

D

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

💡 Hint

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

The Tower of Hanoi solution for 2 disks involves moving disk 1 from A to B, then disk 2 from A to C, then disk 1 from B to C.

🧠 Conceptual

intermediate

Minimum moves required for Tower of Hanoi

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

A 31

B 15

C 16

D 8

💡 Hint

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

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

🔧 Debug

advanced

Identify the error in Tower of Hanoi recursive function

What error will the following Tower of Hanoi function produce when called with n=3? void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n == 0) { std::cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << std::endl; return; } towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); std::cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << std::endl; towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); }

A Outputs correct moves for 3 disks

B Runtime error due to invalid rod names

C Compilation error due to missing return type

D No output, infinite recursion causing stack overflow

💡 Hint

Check the base case condition for recursion termination.

The base case checks for n == 0 but tries to move disk 1, so recursion never stops for n > 0 causing infinite recursion.

❓ Predict Output

advanced

Number of moves printed for 3 disks

How many moves will be printed by the Tower of Hanoi function when called with 3 disks?

DSA C++

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        std::cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << std::endl;
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    std::cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << std::endl;
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    towerOfHanoi(3, 'A', 'C', 'B');
    return 0;
}

A 7

B 8

C 6

D 9

💡 Hint

Use the formula 2^n - 1 to find the number of moves.

For 3 disks, minimum moves = 2^3 - 1 = 7 moves printed.

🚀 Application

expert

Time complexity of Tower of Hanoi algorithm

What is the time complexity of the Tower of Hanoi recursive algorithm for n disks?

A O(n^2)

B O(n)

C O(2^n)

D O(n!)

💡 Hint

Consider how the number of moves grows as n increases.

The Tower of Hanoi algorithm requires 2^n - 1 moves, so time complexity is exponential O(2^n).

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