You get a whole number n. Return the moves that solve the Tower of Hanoi puzzle with n disks.
The puzzle has three pegs, numbered 1, 2 and 3. At the start, all n disks sit on peg 1. Each disk is smaller than the one below it.
Move the whole stack to peg 3. Each move takes the top disk of one peg and puts it on another peg. A disk may never sit on a smaller disk.
Use as few moves as possible. There is only one way to do that.
Write each move as a pair [from, to]: the peg the disk leaves, then the peg it lands on. Return the moves in the order you make them.
Solve it with a recursive function.
Example 1:
Input: n = 1 Output: [[1,3]] Explanation: The only disk goes straight to peg 3.
Example 2:
Input: n = 2 Output: [[1,2],[1,3],[2,3]] Explanation: The small disk moves to peg 2, out of the way. The big disk moves to peg 3. The small disk moves onto the big one.
Example 3:
Input: n = 3 Output: [[1,3],[1,2],[3,2],[1,3],[2,1],[2,3],[1,3]] Explanation: The picture above shows the start. Moves 1 to 3 stack the two small disks on peg 2. Move 4 takes the biggest disk to peg 3. Moves 5 to 7 stack the two small disks on top of it.
Constraints:
nis a whole number from 1 to 16.
Your solution should run in O(2ⁿ) time.
Hints:
Think about the biggest disk. It can only move when every other disk is off it, and off its target peg too. Where must the other disks be at that moment?
Moving the other n - 1 disks out of the way is the same puzzle with one disk less. Write a helper that moves k disks from any peg to any other peg, with the third peg as a spare. It calls itself twice: once before its biggest disk moves, and once after.
A call for n disks makes one move and two calls for n - 1 disks. That adds up to 2n - 1 moves: O(2n) time.
The calls go at most n deep, so besides the answer the extra space is O(n).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
