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

function towerOfHanoi(n, fromRod, toRod, auxRod) {
  if (n === 1) {
    console.log(`Move disk 1 from rod ${fromRod} to rod ${toRod}`);
    return;
  }
  towerOfHanoi(n - 1, fromRod, auxRod, toRod);
  console.log(`Move disk ${n} from rod ${fromRod} to rod ${toRod}`);
  towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}
towerOfHanoi(2, 'A', 'C', 'B');

A

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

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 A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C

💡 Hint

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

The Tower of Hanoi solution for 2 disks moves 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 with 4 disks?

A 15

B 8

C 16

D 31

💡 Hint

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

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

❓ Predict Output

advanced

Output of Tower of Hanoi moves for 3 disks with custom rods

What is the output of the following Tower of Hanoi function call for 3 disks with rods labeled X, Y, Z?

DSA Javascript

function towerOfHanoi(n, fromRod, toRod, auxRod) {
  if (n === 1) {
    console.log(`Move disk 1 from rod ${fromRod} to rod ${toRod}`);
    return;
  }
  towerOfHanoi(n - 1, fromRod, auxRod, toRod);
  console.log(`Move disk ${n} from rod ${fromRod} to rod ${toRod}`);
  towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}
towerOfHanoi(3, 'X', 'Z', 'Y');

A

Move disk 1 from rod X to rod Y
Move disk 2 from rod X to rod Z
Move disk 1 from rod Y to rod Z
Move disk 3 from rod X to rod Z
Move disk 1 from rod Y to rod X
Move disk 2 from rod Z to rod Y
Move disk 1 from rod X to rod Y

B

Move disk 1 from rod X to rod Z
Move disk 2 from rod X to rod Y
Move disk 1 from rod Z to rod Y
Move disk 3 from rod X to rod Z
Move disk 1 from rod Y to rod X
Move disk 2 from rod Y to rod Z
Move disk 1 from rod X to rod Z

C

Move disk 1 from rod X to rod Y
Move disk 2 from rod X to rod Y
Move disk 1 from rod Y to rod Z
Move disk 3 from rod X to rod Z
Move disk 1 from rod Y to rod X
Move disk 2 from rod Y to rod Z
Move disk 1 from rod X to rod Z

D

Move disk 1 from rod X to rod Y
Move disk 2 from rod X to rod Z
Move disk 1 from rod Y to rod Z
Move disk 3 from rod X to rod Y
Move disk 1 from rod Z to rod X
Move disk 2 from rod Z to rod Y
Move disk 1 from rod X to rod Y

💡 Hint

Follow the recursive pattern carefully with the given rod names.

The correct sequence for 3 disks moving from X to Z using Y as auxiliary is option B.

🔧 Debug

advanced

Identify the error in Tower of Hanoi implementation

What error will the following Tower of Hanoi code produce when called with n=2?

DSA Javascript

function towerOfHanoi(n, fromRod, toRod, auxRod) {
  if (n === 1) {
    console.log(`Move disk 1 from rod ${fromRod} to rod ${toRod}`)
    return
  }
  towerOfHanoi(n - 1, fromRod, auxRod, toRod)
  console.log(`Move disk ${n} from rod ${fromRod} to rod ${toRod}`)
  towerOfHanoi(n - 1, auxRod, toRod, fromRod)
}
towerOfHanoi(2, 'A', 'C', 'B')

A ReferenceError due to undefined variable

B SyntaxError due to missing semicolons

C No error, outputs correct moves

D No output because function never returns

💡 Hint

JavaScript does not require semicolons strictly; check function logic.

The code runs correctly and outputs the moves for 2 disks; missing semicolons do not cause errors here.

🧠 Conceptual

expert

Time complexity of Tower of Hanoi algorithm

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

A O(2^n)

B O(n^2)

C O(n)

D O(n!)

💡 Hint

The number of moves doubles with each additional disk minus one.

The Tower of Hanoi algorithm has exponential time complexity O(2^n) because the moves double with each disk added.

Practice

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

easy

A. 7

B. 6

C. 8

D. 9

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 A

4. Quick Check:

   2^3 - 1 = 7 [OK]

Hint: Use formula 2^n - 1 for minimum moves [OK]

Common Mistakes:

• Forgetting to subtract 1
• Using n 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 JavaScript?

easy

A. if (n < 0) return;

B. if (n === 1) moveDisk();

C. if (n > 1) return;

D. if (n === 0) return;

Solution

1. Step 1: Identify base case for recursion

   The recursion stops when there are no disks to move, i.e., n === 0.

2. Step 2: Check the options

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

3. Final Answer:

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

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 incorrectly
• Not stopping recursion causing infinite calls
• Using invalid conditions like n < 0

3. What will be the output sequence of moves for 2 disks in the Tower of Hanoi problem using this code snippet?

function towerOfHanoi(n, from, to, aux) {
  if (n === 0) return;
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}
towerOfHanoi(2, 'A', 'C', 'B');

medium

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

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

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

D. "Move disk 1 from A to C"
"Move disk 2 from A to B"
"Move disk 1 from C to B"

Solution

1. Step 1: Trace recursive calls for n=2

   First move disk 1 from A to B, then disk 2 from A to C, then disk 1 from B to C.

2. Step 2: Match output 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 exact sequence of moves printed by the code.

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 C

4. Quick Check:

   Correct move sequence for 2 disks = "Move disk 1 from A to B" "Move disk 2 from A to C" "Move disk 1 from B to C" [OK]

Hint: Follow recursion calls step-by-step [OK]

Common Mistakes:

• Mixing source and auxiliary rods
• Confusing disk numbers in moves
• Ignoring order of recursive calls

4. Identify the error in this Tower of Hanoi recursive function and select the fix:

function towerOfHanoi(n, from, to, aux) {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, to, aux);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}

medium

A. Swap 'to' and 'aux' in the first recursive call

B. Change base case to n === 0

C. Remove the second recursive call

D. Add an extra console.log before recursion

Solution

1. Step 1: Analyze recursive calls

   The first recursive call should move n-1 disks from 'from' to 'aux' using 'to' as auxiliary, but here 'to' and 'aux' are swapped.

2. Step 2: Correct the argument order

   Swapping 'to' and 'aux' in the first recursive call fixes the logic to move disks correctly.

3. Final Answer:

   Swap 'to' and 'aux' in the first recursive call -> Option A

4. Quick Check:

   Correct recursive call order fixes error [OK]

Hint: Check recursive call parameters carefully [OK]

Common Mistakes:

• Mixing auxiliary and target rods
• Incorrect base case causing infinite recursion
• Removing necessary recursive calls

5. You want to solve the Tower of Hanoi problem for 4 disks but only want to print moves where disk 1 is moved. How would you modify this function?

function towerOfHanoi(n, from, to, aux) {
  if (n === 0) return;
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}

hard

A. Change base case to n === 1 and print only then

B. Add an if condition to print only when n === 1 inside the function

C. Remove recursive calls and print only disk 1 move

D. Print all moves but filter output outside the function

Solution

1. Step 1: Understand the requirement

   We want to print moves only when disk 1 moves, but still perform all recursive calls to solve the problem.

2. Step 2: Modify print statement with condition

   Add an if condition to print only when n === 1, so other moves are not printed but recursion continues.

3. Final Answer:

   Add an if condition to print only when n === 1 inside the function -> Option B

4. Quick Check:

   Conditional print inside recursion solves problem [OK]

Hint: Use if (n === 1) to print selectively [OK]

Common Mistakes:

• Changing base case breaks recursion
• Removing recursive calls stops solution
• Filtering output outside misses recursion logic