Tower of Hanoi — Aptitude Question
Tower of Hanoi: What is the minimum number of moves needed to solve the Tower of Hanoi puzzle with 6 disks? Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Easy
- Time target: 60 seconds
Question
What is the minimum number of moves needed to solve the Tower of Hanoi puzzle with 6 disks?
Options
- 31
- 36
- 63
- 64
Show the answer and the worked solution
Correct answer: C. 63
Worked solution
- To move n disks you move n − 1 aside, move the largest disk, then move the n − 1 back: M(n) = 2M(n − 1) + 1.
- With M(1) = 1 this solves to M(n) = 2^n − 1.
- For n = 6 that gives 2^6 − 1 = 63 moves.
Answer: 63.
The idea
The recurrence M(n) = 2M(n − 1) + 1 is the archetype of exponential recursion, and 2^n − 1 is worth recognising on sight.
Shortcut. 2⁶ − 1 = 63; the count 2M + 1 is always odd, which rules out 36 and 64 on sight.
Common trap. 64 is 2⁶ without the −1, from misremembering the formula 2ⁿ − 1.
All Data Structures & Algorithms questions · placement mock tests