167. Iterative Tower of Hanoi - Minimum Number of Moves

Given n disks stacked on the first of three pegs, find the minimum number of single-disk moves needed to move the entire stack to the third peg, following the standard Tower of Hanoi rules (move one disk at a time, never place a larger disk on a smaller one).

Input: The input is a single line containing the integer n - the number of disks. Output: Print a single integer - the minimum number of moves required.

0 <= n <= 60

This problem's title mentions 'iterative' specifically because the classic Tower of Hanoi is normally taught RECURSIVELY - being asked for an iterative (stack-based) simulation, or simply the closed-form count, tests whether you understand the underlying structure beyond just reciting the recursive solution.

Find the minimum number of moves needed to move a stack of n disks from one peg to another, following the classic Tower of Hanoi rules. Brute force: Actually simulate every single move of an optimal Tower of Hanoi solution (recursively or iteratively) and count them - this works but does far more work than necessary just to get a COUNT, when a direct formula gives the same answer instantly. Optimised: The classic recursive Tower of Hanoi solution's move count follows the recurrence moves(n) = 2*moves(n-1) + 1 (move n-1 disks aside, move the biggest disk, move the n-1 disks back on top) - solving this recurrence directly yields the closed-form 2^n - 1, letting you skip simulating any moves at all if only the COUNT is needed.

Actually carry out the iterative Tower of Hanoi algorithm (using three explicit peg stacks and the fixed legal alternating-move pattern between them) disk by disk, counting every single-disk move as it's performed until all disks sit on the third peg. This directly answers the question by simulation, mirroring what 'iterative Tower of Hanoi' usually means as an exercise, but the number of moves performed is exponential in n, so simulating them all is wasteful just to obtain a count. Time: O(2^n) Space: O(n)

Recognize the recurrence moves(n) = 2 * moves(n-1) + 1 with moves(0) = 0, and compute it with a simple loop from 1 up to n instead of simulating any actual disk moves. This avoids ever generating the exponential move sequence itself, computing only the count, which is a large improvement, though it still does n sequential doubling steps and needs care about integer overflow for larger n. Time: O(n) Space: O(1)

The minimum number of moves for n disks is exactly 2^n - 1, so this can be computed directly with fast exponentiation (or a single bit-shift) instead of looping n times. Since n can be up to 60, 2^60 - 1 exceeds the range of a standard 53-bit safe double-precision integer, so the computation should use a BigInt (or a 64-bit integer type in other languages) to get an exact answer. This gives the result in effectively constant time while guaranteeing correctness at the upper end of the constraint range. Time: O(1) (or O(log n) with fast exponentiation) Space: O(1)

1. Recognize the well-known closed-form result: the minimum number of moves for n disks is exactly 2^n - 1. 2. This can be computed directly with the formula, OR simulated iteratively using an explicit stack (mimicking what the classic recursive solution does, but without actual recursion).

Time: O(1) with the direct formula (or O(log n) if computed via fast exponentiation for very large n); O(2^n) if actually simulating every move. Space: O(1) for the formula-based approach.

n = 0 (0 moves); n = 60, where the result 2^60 - 1 requires a 64-bit integer since it overflows a 32-bit int.

Be ready to derive the 2^n - 1 formula from the recurrence relation, not just state it from memory - interviewers often want to see the derivation (moves(n) = 2*moves(n-1)+1, with moves(0)=0) as proof of genuine understanding.