Problem Description
You are given n children standing in a line numbered from 0 to n - 1. Initially, child 0 holds a ball and passes it to the right every second. When the ball reaches either end (child 0 or child n - 1), the direction is reversed. Given k seconds, determine the number of the child who has the ball at the end.
Key Insights
- The ball moves in a back-and-forth (zigzag) pattern along the line of children.
- The path repeats every 2*(n - 1) seconds due to the reversal at both ends.
- Using modulo arithmetic can directly compute the position without simulating each second.
- The final position can be determined: if remainder ≤ n - 1, that remainder is the index; otherwise, the index is reflected using (2*(n - 1) - remainder).
Space and Time Complexity
Time Complexity: O(1)
Space Complexity: O(1)
Solution
The solution utilizes mathematical observation of the ball's movement. Instead of simulating each second, we observe that the ball's path is periodic with a period of T = 2*(n - 1). By taking k modulo T, we get an effective time step that falls within one complete cycle of the back-and-forth movement. If this value (let's call it pos) is less than or equal to n - 1, the ball is moving to the right at that moment and the child with index pos holds the ball. Otherwise, the ball is moving to the left and the current holder is at the reflected index computed as (2*(n - 1) - pos).
Data structures used:
- Simple integer arithmetic operations.
Algorithmic approach:
- Compute pos = k mod (2*(n - 1)).
- Check if pos is within the left-to-right phase or the right-to-left phase.
- Return pos or (2*(n - 1) - pos) accordingly.
No tricky edge cases arise since the constraints ensure proper inputs with n >= 2.