Tower of Hanoi Problem in DSA Java - Time & Space Complexity

Time Complexity: Tower of Hanoi Problem

O(2^n)

Understanding Time Complexity

We want to understand how the number of moves grows as we increase the number of disks in the Tower of Hanoi problem.

How does the work needed change when we add more disks?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void towerOfHanoi(int n, char fromRod, char toRod, char auxRod) {
    if (n == 1) {
        System.out.println("Move disk 1 from " + fromRod + " to " + toRod);
        return;
    }
    towerOfHanoi(n - 1, fromRod, auxRod, toRod);
    System.out.println("Move disk " + n + " from " + fromRod + " to " + toRod);
    towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}

This code moves n disks from one rod to another using recursion and an auxiliary rod.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls that move smaller stacks of disks.
• How many times: Each call makes two recursive calls with n-1 disks, plus one move operation.

How Execution Grows With Input

Each time we add a disk, the number of moves roughly doubles and then adds one more move.

Input Size (n)	Approx. Operations (moves)
1	1
2	3
3	7
4	15
5	31

Pattern observation: The moves grow exponentially, doubling with each added disk.

Final Time Complexity

Time Complexity: O(2^n)

This means the number of moves grows very fast, doubling for each extra disk added.

Common Mistake

[X] Wrong: "The time grows linearly with the number of disks because we just move each disk once."

[OK] Correct: Actually, disks are moved multiple times in a recursive pattern, so the total moves double with each added disk, not just increase by one.

Interview Connect

Understanding this problem helps you think about recursion and exponential growth, which are common in many coding challenges.

Self-Check

"What if we changed the problem to move disks iteratively without recursion? How would the time complexity change?"

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