Tower of Hanoi Problem in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA C++

void moveDisk(char [1], char dest) {
    std::cout << "Move disk from " << [1] << " to " << dest << std::endl;
}

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

Asrc

Bstart

Cfrom

Dsource

Attempts:

3 left

💡 Hint

Common Mistakes

Using a variable name not defined in the function parameters.

The variable representing the source peg is named 'source' in the function parameter.

2fill in blank

medium

Complete the recursive call to move n-1 disks from source to auxiliary peg.

DSA C++

void towerOfHanoi(int n, char source, char dest, char aux) {
    if (n == 1) {
        moveDisk(source, dest);
        return;
    }
    towerOfHanoi([1], source, aux, dest);
    moveDisk(source, dest);
    towerOfHanoi(n - 1, aux, dest, source);
}

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

An - 1

Bn + 1

C1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of n-1 in the recursive call.

Using n+1 which is invalid.

The recursive call moves n-1 disks to the auxiliary peg before moving the largest disk.

3fill in blank

hard

Fix the error in the base case condition to stop recursion correctly.

DSA C++

void towerOfHanoi(int n, char source, char dest, char aux) {
    if (n [1] 1) {
        moveDisk(source, dest);
        return;
    }
    towerOfHanoi(n - 1, source, aux, dest);
    moveDisk(source, dest);
    towerOfHanoi(n - 1, aux, dest, source);
}

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

A==

B>

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' or '<' which causes incorrect recursion termination.

Using '!=' which never stops recursion properly.

The base case is when n equals 1, so the condition should be 'n == 1'.

4fill in blank

hard

Fill both blanks to correctly call the recursive function for moving disks.

DSA C++

towerOfHanoi([1], source, aux, [2]);

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

An - 1

Bdest

Csource

Daux

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of n-1.

Swapping source and destination pegs.

The first argument is n-1 disks, and the last argument is the destination peg.

5fill in blank

hard

Fill all three blanks to complete the recursive calls and moveDisk call in the Tower of Hanoi function.

DSA C++

towerOfHanoi([1], source, aux, dest);
moveDisk(source, [2]);
towerOfHanoi([3], aux, dest, source);

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

An - 1

Bdest

Dsource

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of n-1 in recursive calls.

Swapping source and destination in moveDisk.

The first and third recursive calls move n-1 disks, and moveDisk moves the largest disk from source to destination.

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