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

function towerOfHanoi(n: number, fromRod: string, toRod: string, auxRod: string, moves: string[] = []): string[] {
  if (n === 1) {
    moves.push(`Move disk 1 from ${fromRod} to ${toRod}`);
    return moves;
  }
  towerOfHanoi(n - 1, fromRod, auxRod, toRod, moves);
  moves.push(`Move disk ${n} from ${fromRod} to ${toRod}`);
  towerOfHanoi(n - 1, auxRod, toRod, fromRod, moves);
  return moves;
}

const result = towerOfHanoi(2, 'A', 'C', 'B');
console.log(result.join('\n'));

A

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

B 31

C 15

D 16

💡 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.

🔧 Debug

advanced

Identify the error in Tower of Hanoi implementation

What error will this Tower of Hanoi code produce when called with n=3?

DSA Typescript

function towerOfHanoi(n: number, fromRod: string, toRod: string, auxRod: string): void {
  if (n === 0) {
    return;
  }
  towerOfHanoi(n - 1, fromRod, auxRod, toRod);
  console.log(`Move disk ${n} from ${fromRod} to ${toRod}`);
  towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}

towerOfHanoi(3, 'A', 'C', 'B');

A No error, outputs correct moves

B Stack overflow error due to infinite recursion

C TypeError because of wrong parameter types

D SyntaxError due to missing return statement

💡 Hint

Check the base case and recursive calls carefully.

The base case n===0 stops recursion correctly, so no error occurs and moves print properly.

❓ Predict Output

advanced

Number of moves printed for 3 disks

How many moves will be printed by this Tower of Hanoi function call with 3 disks?

DSA Typescript

function towerOfHanoi(n: number, fromRod: string, toRod: string, auxRod: string, moves: string[] = []): string[] {
  if (n === 1) {
    moves.push(`Move disk 1 from ${fromRod} to ${toRod}`);
    return moves;
  }
  towerOfHanoi(n - 1, fromRod, auxRod, toRod, moves);
  moves.push(`Move disk ${n} from ${fromRod} to ${toRod}`);
  towerOfHanoi(n - 1, auxRod, toRod, fromRod, moves);
  return moves;
}

const result = towerOfHanoi(3, 'A', 'C', 'B');
console.log(result.length);

A 6

B 8

C 9

D 7

💡 Hint

Minimum moves for n disks is 2^n - 1.

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

🚀 Application

expert

Calculate total moves for n disks using formula

Which TypeScript function correctly calculates the minimum number of moves required to solve Tower of Hanoi for n disks?

A function minMoves(n: number): number { return Math.pow(2, n) - 1; }

B function minMoves(n: number): number { return 2 * n + 1; }

C function minMoves(n: number): number { return n * n - 1; }

D function minMoves(n: number): number { return n * 2 - 1; }

💡 Hint

Recall the formula for minimum moves is 2^n - 1.

Option A correctly implements the formula 2^n - 1 for minimum moves.

Practice

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

easy

A. 6

B. 7

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 B

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
• Confusing moves with disks

2. Which of the following is the correct TypeScript function signature for solving Tower of Hanoi recursively?

easy

A. function towerOfHanoi(n: number, from: string, to: string, aux: string): void

B. function towerOfHanoi(n: string, from: number, to: number, aux: number): number

C. function towerOfHanoi(n: number, from: number, to: number): void

D. function towerOfHanoi(n: number): string

Solution

1. Step 1: Identify parameters needed for Tower of Hanoi

   We need number of disks (number), source peg (string), destination peg (string), and auxiliary peg (string).

2. Step 2: Match with function signature

   function towerOfHanoi(n: number, from: string, to: string, aux: string): void matches all parameters with correct types and returns void as it prints moves.

3. Final Answer:

   function towerOfHanoi(n: number, from: string, to: string, aux: string): void -> Option A

4. Quick Check:

   Correct parameters and return type [OK]

Hint: Check parameter types and count carefully [OK]

Common Mistakes:

• Using wrong parameter types
• Missing auxiliary peg parameter
• Wrong return type

3. What will be the output of the following TypeScript code snippet for Tower of Hanoi with 2 disks?

function towerOfHanoi(n: number, from: string, to: string, aux: string): void {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    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 1 from A to C
Move disk 2 from A to B
Move disk 1 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 B to C
Move disk 2 from A to C
Move disk 1 from A to B

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

Solution

1. Step 1: Trace first recursive call with n=2

   Call towerOfHanoi(1, 'A', 'B', 'C') prints "Move disk 1 from A to B".

2. Step 2: Print move for disk 2

   Prints "Move disk 2 from A to C".

3. Step 3: Trace second recursive call with n=1

   Call towerOfHanoi(1, 'B', 'C', 'A') prints "Move disk 1 from B to C".

4. Final Answer:

   Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C -> Option D

5. Quick Check:

   Follow recursion steps carefully [OK]

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

Common Mistakes:

• Mixing source and auxiliary pegs
• Printing moves in wrong order
• Confusing disk numbers

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

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

medium

A. Change base case to if (n === 1) and print move for disk 1

B. Change base case to if (n === 0) and remove print statement

C. Remove recursive calls and only print moves

D. Change print statement to print disk 0

Solution

1. Step 1: Analyze base case condition

   Base case should be when n equals 1, not 0, because disk numbering starts at 1.

2. Step 2: Fix base case and print statement

   Change if (n === 0) to if (n === 1) and print move for disk 1.

3. Final Answer:

   Change base case to if (n === 1) and print move for disk 1 -> Option A

4. Quick Check:

   Base case must handle smallest disk [OK]

Hint: Base case is n === 1, not zero [OK]

Common Mistakes:

• Using n === 0 as base case
• Printing move for disk 1 in wrong place
• Skipping base case

5. You want to solve Tower of Hanoi for 4 disks but only print moves where disk 1 is moved. Which modification to the recursive function is correct?

hard

A. Print all moves and filter disk 1 moves after recursion

B. Remove all recursive calls except for n=1

C. Add condition to print only if disk number is 1 inside the print statement

D. Change base case to n=2 and print only disk 1 moves

Solution

1. Step 1: Understand requirement to print only disk 1 moves

   We must keep recursion intact but print moves only when disk number is 1.

2. Step 2: Modify print statement with condition

   Add if (n === 1) before printing move to filter only disk 1 moves.

3. Final Answer:

   Add condition to print only if disk number is 1 inside the print statement -> Option C

4. Quick Check:

   Filter print, keep recursion [OK]

Hint: Use if condition inside print to filter moves [OK]

Common Mistakes:

• Removing recursive calls breaks solution
• Filtering moves after recursion wastes time
• Changing base case incorrectly