Loading...
Loading...
Loading...
A support ticket moves through a chain of stations. Station i passes the ticket to the station given at position i of the list, and -1 means the ticket leaves the chain. The ticket starts at station 0 and the chain has no loop. Print the number of the middle station. If the chain has an even number of stations, print the second of the two middle stations. Use a slow and a fast pointer.
Example 1
Input
1 2 3 4 -1
Output
2
Stations in order are 0, 1, 2, 3, 4. The middle is 2.
Example 2
Input
1 2 3 -1
Output
2
Try the problem first. Open one hint at a time.
Move slow one station and fast two stations each round.
Stop when fast is at -1 or its next station is -1, so the two-step move never leaves the chain.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor