339. Disc Tower Moves
A temple has three pegs numbered 1, 2 and 3. Peg 1 carries a tower of n discs with different widths, the widest at the bottom. The monks must carry the whole tower to peg 3, moving one disc at a time from the top of one peg to the top of another, and never placing a wider disc on a narrower one.
Return the shortest sequence of moves, written as an array of pairs [from, to] in the order they are carried out. The shortest sequence is unique, so there is only one correct answer; it always has 2^n - 1 moves. For n = 1 the answer is [[1, 3]].
Example 1
- Input:
- n = 3
- Output:
- [[1,3],[1,2],[3,2],[1,3],[2,1],[2,3],[1,3]]
- Explanation:
Seven moves are needed: the small discs go 1 to 3, 1 to 2, 3 to 2, then the widest goes 1 to 3, then the rest move 2 to 1, 2 to 3, 1 to 3.
Example 2
- Input:
- n = 4
- Output:
- [[1,2],[1,3],[2,3],[1,2],[3,1],[3,2],[1,2],[1,3],[2,3],[2,1],[3,1],[2,3],[1,2],[1,3],[2,3]]
- Explanation:
Fifteen moves are needed. The top three discs first travel to peg 2, the widest goes to peg 3, and the three discs follow to peg 3.
Constraints
1 ≤ n ≤ 10
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(2^n)
- Space
- O(2^n)