Problem Description
You are given two positive integers n and k. There are n children numbered from 0 to n - 1 standing in a queue in order from left to right. Initially, child 0 holds a ball and the direction of passing the ball is towards the right direction. After each second, the child holding the ball passes it to the child next to them. Once the ball reaches either end of the line, i.e. child 0 or child n - 1, the direction of passing is reversed. Return the number of the child who receives the ball after k seconds.
Key Insights
- The ball starts with child 0 and moves to the right.
- When the ball reaches the last child (n - 1), it reverses direction and starts moving to the left.
- The ball's position can be determined mathematically based on the value of k and the number of children n, without simulating each second.
Space and Time Complexity
Time Complexity: O(1)
Space Complexity: O(1)
Solution
To solve the problem, we can utilize the concept of modulo arithmetic to determine the position of the ball after k seconds. The ball will bounce back and forth between the two ends of the line. We can calculate the effective number of moves by considering the total number of moves k modulo the total number of "bounce" moves, which is 2 * (n - 1) (the ball moves to the right and then back to the left). This approach eliminates the need for iterative simulation.