402. Recursion-Tower of Hanoi

0

Medium

Google Tower of Hanoi.
Solve the Tower of Hanoi problem by shifting all rings from one peg to another using a helper peg.
The rings are initially arranged in ascending order, with the smallest ring on top.
No larger ring can be placed on top of a smaller ring.
a. Create a recursive function that prints the necessary steps to solve the Tower of Hanoi problem for a given number of discs.
b. Develop a recursive function that returns the total number of steps required to solve the Tower of Hanoi problem for a given number of discs.
Let T1 represent the source tower, T2 represent the destination tower, and T3 represent the auxiliary tower.

Input Format

Enter the number of discs

Output Format

Display the steps required to solve the tower and also print the total number of steps required

Example

Input

2

Output

Move the 1st disc from T1 to T3
Move the 2nd disc from T1 to T2
Move the 1st disc from T3 to T2
3

Constraints

None

Loading...

View Submissions

Console