Tower of Hanoi — Editorial

Opening the reading…

Intuitionwhy one largest-disk move determines the entire recurrence

The largest disk cannot move until every one of the n - 1 smaller disks has left the source rod. Those smaller disks must be stacked safely on the auxiliary rod, which is exactly the same problem with one fewer disk. After the largest disk moves once to the destination, the n - 1 smaller disks must move again, this time from the auxiliary rod to the destination.

If M(n) is the minimum number of moves for n disks, the required process has three unavoidable parts: M(n - 1) moves before the largest disk, one move for that largest disk, and M(n - 1) moves afterward. Therefore M(n) = 2M(n - 1) + 1, with M(0) = 0. Expanding the recurrence gives M(n) = 2^n - 1, so counting moves never requires constructing the sequence.

Approach

Define the minimum count for zero disks as 0, because an empty stack already satisfies the goal and requires no move.

Observe that moving the largest disk requires solving the n - 1 disk problem first, because every smaller disk must be off the source rod.

Count the largest disk's move as one, because it must travel from the source rod to the destination exactly once in any valid solution.

Solve the remaining n - 1 disk problem after the largest disk moves, because those disks still have to reach the destination from the auxiliary rod.

Combine the parts as M(n) = M(n - 1) + 1 + M(n - 1), or 2M(n - 1) + 1; omitting either smaller-stack transfer counts only half of the necessary work.

Use the closed form M(n) = 2^n - 1 and compute the power by starting at 1 and doubling n times, because generating actual moves would do unnecessary work when only the count is requested.

Return moves - 1 after the loop; starting from 1 makes the zero-disk case produce 1 - 1 = 0 without a separate special case.

Complexitythe count is computed without storing a move sequence

MEASURE	BOUND	WHY
Time	O(n)	The loop doubles one integer exactly n times, and each iteration performs constant work. No disk arrangement or move sequence is generated, so no operation is repeated over the rods.
Space	O(1) extra	Only the integer holding the current power and the final count are stored; the required output is a single integer, so there is no output storage to exclude. The bound stays O(1) for every input shape, unlike the recursive formulation whose call stack reaches O(n) in its deepest shape.

Annotated solutionC++ · iterative closed form · count only, no simulated moves

CPPDouble the move count n times, then subtract one to evaluate 2^n - 1.

#include <vector>

using namespace std;

class Solution {
public:
    int towerOfHanoi(int n) {
        int moves = 1;
        for (int i = 0; i < n; ++i) {
            moves *= 2;
        }
        return moves - 1;
    }
};

The initial value moves = 1 represents 2^0, not the answer for one disk. Each loop iteration advances the exponent by one, so after n iterations moves is 2^n. Subtracting one at the return converts that power into the required minimum count and also handles n = 0 naturally.

The recursive alternativethe direct proof shape, when showing the construction matters

A recursive implementation mirrors the unavoidable process directly: solve n - 1, count the largest disk's move, then solve n - 1 again. It is a reasonable way to derive and explain the formula, but it is not an optimisation for this task. It performs O(n) calls and uses O(n) call-stack space, whereas the iterative closed form keeps only the current count.

CPPRecursive recurrence: two smaller-stack counts plus the largest disk's one move.

#include <vector>

using namespace std;

class Solution {
public:
    int towerOfHanoi(int n) {
        return countMoves(n);
    }

private:
    int countMoves(int disks) {
        if (disks == 0) {
            return 0;
        }
        return 2 * countMoves(disks - 1) + 1;
    }
};

This recursive version is a different arrangement rather than a better algorithm. Its base case states the empty-stack fact, and its return line states the recurrence exactly. With n limited to 20, it remains safe here, but the iterative form is preferable when the judge asks only for the count because it removes the call stack and makes the closed form explicit.