Log inSign up
mediumGeeksforGeeksNot Started

Tower of Hanoi

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

The tower of Hanoi is a famous puzzle where we have three rods and N disks. The objective of the puzzle is to move the entire stack of disks to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time. 2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack. 3. No larger disk may be placed on top of a smaller disk.

Given the number of disks N, the source rod from_rod, the target rod to_rod, and the auxiliary rod aux_rod, print all steps of the movement and return the total number of moves.

Example 1 · 2 Disks:

Input: N = 2, from_rod = 1, to_rod = 3, aux_rod = 2
Output: 3
Explanation: Move disk 1 from rod 1 to rod 2 Move disk 2 from rod 1 to rod 3 Move disk 1 from rod 2 to rod 3 Total moves: 3 (22 - 1)

Example 2 · 3 Disks:

Input: N = 3, from_rod = 1, to_rod = 3, aux_rod = 2
Output: 7
Explanation: Move disk 1 from rod 1 to rod 3 Move disk 2 from rod 1 to rod 2 Move disk 1 from rod 3 to rod 2 Move disk 3 from rod 1 to rod 3 Move disk 1 from rod 2 to rod 1 Move disk 2 from rod 2 to rod 3 Move disk 1 from rod 1 to rod 3 Total moves: 7 (23 - 1)

Constraints:

  • 1 <= N <= 16
  • from_rod, to_rod, aux_rod are distinct integers from 1 to 3.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mechanics of Divide and Conquer on hierarchical stack structures.
  • Derive and solve the recurrence relation T(N) = 2T(N-1) + 1.
  • Implement both recursive and iterative (explicit 3-stack) solutions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Moving objects sequentially with strict ordering constraints (LIFO / non-increasing size)
  • Optimal substructure: moving N objects is defined in terms of moving N-1 objects
  • Exponential growth of steps (2N - 1)

Algorithmic Decision Tree:

  • Base case: N == 0 (do nothing) or N == 1 (move single disk directly).
  • Recursively reduce N-disk problem to two (N-1)-disk subproblems around 1 single-disk move.

Connected Patterns:

Gray Code GenerationBinary Recursion TreeDivide and Conquer

1. Bitwise / Gray Code Mathematical Generation

Intuition

For any move k (from 1 to 2N - 1), the disk to move is the 1-based index of the lowest set bit of k (__builtin_ctz(k) + 1). Even-sized and odd-sized disks alternate directions in a cyclic manner.

When to apply: When you want to compute individual move transitions in O(1) time without recursion.

Algorithm

  1. Calculate total moves = 2N - 1.
  2. For step k from 1 to 2N - 1:
  3. - Disk index = (k & -k) index.
  4. - Move disk between source and destination following parity direction rules.
  5. Return total moves count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <cmath>
3
4using namespace std;
5
6class Solution {
7public:
8 long long tohBitwise(int n, int from, int to, int aux) {
9 long long totalMoves = (1LL << n) - 1;
10 for (long long i = 1; i <= totalMoves; i++) {
11 int disk = __builtin_ctzll(i) + 1;
12 // Print movement according to Gray code transitions
13 int src = (i & (i - 1)) % 3;
14 int dst = ((i | (i - 1)) + 1) % 3;
15 // Map 0, 1, 2 to from, to, aux
16 }
17 return totalMoves;
18 }
19};
20
21int main() {
22 Solution sol;
23 cout << "Total moves: " << sol.tohBitwise(3, 1, 3, 2) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(2^N) — Generates exactly 2N - 1 steps with O(1) bitwise operations per step.
  • Space complexity: O(1) — Uses constant auxiliary space.

2. Iterative Simulation using 3 Peg Stacks

Intuition

For even N, swap destination and auxiliary rods. For total 2N - 1 moves, alternate legal moves between rods (Src, Dest), (Src, Aux), and (Aux, Dest).

When to apply: When an iterative, non-recursive stack simulation is explicitly requested.

Algorithm

  1. Initialize 3 stacks: src, dest, aux with disks N down to 1 in src.
  2. If N is even, swap dest and aux rods.
  3. Loop i from 1 to 2N - 1:
  4. - If i % 3 == 1: make legal move between src and dest.
  5. - If i % 3 == 2: make legal move between src and aux.
  6. - If i % 3 == 0: make legal move between aux and dest.
  7. Return total moves.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3#include <cmath>
4
5using namespace std;
6
7class Solution {
8 void moveDisksBetweenTwoPoles(stack<int>& src, stack<int>& dest, int s, int d) {
9 if (src.empty()) {
10 src.push(dest.top());
11 dest.pop();
12 cout << "move disk " << src.top() << " from rod " << d << " to rod " << s << endl;
13 } else if (dest.empty()) {
14 dest.push(src.top());
15 src.pop();
16 cout << "move disk " << dest.top() << " from rod " << s << " to rod " << d << endl;
17 } else if (src.top() > dest.top()) {
18 src.push(dest.top());
19 dest.pop();
20 cout << "move disk " << src.top() << " from rod " << d << " to rod " << s << endl;
21 } else {
22 dest.push(src.top());
23 src.pop();
24 cout << "move disk " << dest.top() << " from rod " << s << " to rod " << d << endl;
25 }
26 }
27
28public:
29 long long tohIterative(int n, int from, int to, int aux) {
30 stack<int> src, dest, helper;
31 for (int i = n; i >= 1; i--) src.push(i);
32
33 long long totalMoves = pow(2, n) - 1;
34
35 if (n % 2 == 0) {
36 swap(to, aux);
37 }
38
39 for (int i = 1; i <= totalMoves; i++) {
40 if (i % 3 == 1) moveDisksBetweenTwoPoles(src, dest, from, to);
41 else if (i % 3 == 2) moveDisksBetweenTwoPoles(src, helper, from, aux);
42 else if (i % 3 == 0) moveDisksBetweenTwoPoles(helper, dest, aux, to);
43 }
44
45 return totalMoves;
46 }
47};
48
49int main() {
50 Solution sol;
51 cout << "Total moves: " << sol.tohIterative(3, 1, 3, 2) << endl;
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(2^N) — Executes 2N - 1 iterations with constant time stack checks per move.
  • Space complexity: O(N) — Requires 3 stacks holding at most N elements total.

3. Divide and Conquer (Standard Recursion)

Intuition

The largest disk N cannot move until all N-1 smaller disks are off it and onto the auxiliary rod. Once disk N moves to destination, the N-1 disks can be stacked on top of it.

When to apply: The definitive gold standard solution for Tower of Hanoi.

Algorithm

  1. Function toh(n, from_rod, to_rod, aux_rod):
  2. 1. Base case: If n == 0, return 0 moves.
  3. 2. Recursively call toh(n - 1, from_rod, aux_rod, to_rod) to move top n - 1 disks to helper rod.
  4. 3. Move disk n directly from from_rod to to_rod (print instruction and increment move counter by 1).
  5. 4. Recursively call toh(n - 1, aux_rod, to_rod, from_rod) to transfer the n - 1 disks from helper rod to destination rod.
  6. 5. Return total accumulated moves (2N - 1).

Peg Stacks Disk Transfer Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initial state: Rod 1 has disks [2 (bottom), 1 (top)]
Visual state
Values and pointers at this exact step
stack
TOP
Disk 2
Disk 1
Push adds to the top · Pop removes from the top
Variables at this step
currentMove
0
pending
Move 2 disks from Rod 1 to Rod 3
Why this step matters

Initial state: Rod 1 has disks [2 (bottom), 1 (top)]. Rod 2: [], Rod 3: [].

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 long long toh(int n, int from, int to, int aux) {
8 if (n == 0) return 0;
9
10 // Move n-1 disks from source to aux using to as helper
11 long long moves = toh(n - 1, from, aux, to);
12
13 // Move nth disk from source to destination
14 cout << "move disk " << n << " from rod " << from << " to rod " << to << endl;
15 moves++;
16
17 // Move n-1 disks from aux to to using source as helper
18 moves += toh(n - 1, aux, to, from);
19
20 return moves;
21 }
22};
23
24int main() {
25 Solution sol;
26 int n = 3;
27 long long totalMoves = sol.toh(n, 1, 3, 2);
28 cout << "Total moves: " << totalMoves << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(2^N) — The recurrence relation is T(N) = 2T(N-1) + 1, which expands to 2N - 1 operations.
  • Space complexity: O(N) — The maximum depth of the recursive call stack is N.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Bitwise / Gray Code Mathematical GenerationO(2^N)O(1)Generate transitions directly using binary lowest set bit.Exponential step count
2.Iterative Simulation using 3 Peg StacksO(2^N)O(N)Simulate physical disk legal moves across 3 explicit stack objects.Explicit stack operations
3.Divide and Conquer (Standard Recursion)OptimalO(2^N)O(N)Move N-1 to aux, move N to dest, move N-1 from aux to dest.Exponential recursive branches

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Swapping the helper and destination pegs in the recursive sub-calls.

Pitfall 2:

Not recognizing that minimum moves count is 2N - 1.

Pitfall 3:

Integer overflow for large N when calculating 2N - 1.

Crucial Edge Cases to Validate:

  • N = 1 Disk: 1 move directly from source to destination.
  • Maximum Constraint N = 16: 65535 total moves calculated and executed efficiently.
  • Order of Pegs: Arbitrary peg permutations (e.g. 1 -> 2, 2 -> 3) work identically.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Know how to derive the 2N - 1 formula: Show T(N) = 2T(N-1) + 1 expanding into geometric series summing to 2N - 1.
  2. Draw the 3-disk recursion tree on whiteboard to demonstrate symmetric binary execution.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How many total moves are required to solve Tower of Hanoi for N = 5 disks?

2.What is the auxiliary space complexity of the recursive Tower of Hanoi solution?

Back to DSA Sheet