Tower of Hanoi: count moves

Challenge

Count the moves needed to solve the Towers of Hanoi.

Task

Implement unsigned long long hanoi_moves(int n) that returns the number of single-disk moves required to solve the Towers of Hanoi puzzle for n disks. The classic result is 2^n - 1. Either approach is accepted:

1. Recursively: T(n) = 2 * T(n-1) + 1, with T(0) = 0.
2. Closed form: (1ULL << n) - 1ULL.

Input

n: the number of disks, 0 <= n <= 60 (so the answer fits in unsigned long long).

Output

unsigned long long: 2^n - 1, the number of moves.

Example

hanoi_moves(0)    ->   0
hanoi_moves(1)    ->   1
hanoi_moves(3)    ->   7
hanoi_moves(10)   ->   1023
hanoi_moves(60)   ->   1152921504606846975   (2^60 - 1)

Edge cases

• n == 0 returns 0.
• n == 60 is the largest input and must not overflow.

Rules

• Return unsigned long long. If you use the bit-shift form, shift 1ULL (not 1) so it does not overflow at large n.

Why this matters

Towers of Hanoi is the cleanest demonstration of recursive thinking: to move n disks, first move n-1 to the spare peg, move the largest, then move n-1 back. The closed-form solution (2^n - 1) emerges naturally — a small but real example of how recursion solves exponential problems compactly.

Input format

n: number of disks, in [0, 60].

Output format

unsigned long long: 2^n - 1.

Constraints

Use unsigned long long. Recursive or closed-form both fine.

Starter code

#include <stdint.h>
unsigned long long hanoi_moves(int n) { /* TODO */ return 0; }

Common mistakes

Returning int — overflows at n == 31. Forgetting that recursion past about n == 25 takes noticeable time without memoisation. The closed form is fastest.

Edge cases to handle

n == 0; n == 60; n == 1.

Complexity

Recursive: O(2^n) — but only because the recurrence does 2 calls each level. Closed form: O(1).

Background lessons

• Recursion — base case + smaller subproblem
• Functions

Up next

• Nth Fibonacci
• Factorial