Watch 10 video solutions for Find the Child Who Has the Ball After K Seconds, a easy level problem involving Math, Simulation. This walkthrough by Aryan Mittal has 2,103 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: n = 3, k = 5
Output: 1
Explanation:
| Time elapsed | Children |
|---|---|
0 |
[0, 1, 2] |
1 |
[0, 1, 2] |
2 |
[0, 1, 2] |
3 |
[0, 1, 2] |
4 |
[0, 1, 2] |
5 |
[0, 1, 2] |
Example 2:
Input: n = 5, k = 6
Output: 2
Explanation:
| Time elapsed | Children |
|---|---|
0 |
[0, 1, 2, 3, 4] |
1 |
[0, 1, 2, 3, 4] |
2 |
[0, 1, 2, 3, 4] |
3 |
[0, 1, 2, 3, 4] |
4 |
[0, 1, 2, 3, 4] |
5 |
[0, 1, 2, 3, 4] |
6 |
[0, 1, 2, 3, 4] |
Example 3:
Input: n = 4, k = 2
Output: 2
Explanation:
| Time elapsed | Children |
|---|---|
0 |
[0, 1, 2, 3] |
1 |
[0, 1, 2, 3] |
2 |
[0, 1, 2, 3] |
Constraints:
2 <= n <= 501 <= k <= 50
Note: This question is the same as 2582: Pass the Pillow.
Problem Overview: You have n children standing in a line. A ball starts with child 0 and moves to the next child every second. When the ball reaches either end of the line, the direction reverses. After k seconds, you must determine which child currently holds the ball.
Approach 1: Simulation Approach (Time: O(k), Space: O(1))
This method directly simulates the movement of the ball second by second. Start with the ball at index 0 and maintain a direction variable: +1 when moving right and -1 when moving left. For each second, update the position by adding the direction. When the ball reaches either boundary (0 or n - 1), flip the direction before the next move. After running the loop for k steps, the final index represents the child holding the ball. The logic is straightforward and mirrors the real movement of the ball. However, the runtime grows linearly with k, which becomes inefficient when k is very large.
This approach is essentially a direct simulation of the process. It helps verify correctness and is often the first solution candidates write during interviews.
Approach 2: Mathematical Pattern Approach (Time: O(1), Space: O(1))
The ball's movement forms a repeating pattern. It travels from child 0 to child n-1, then back to 0. One full cycle therefore contains 2 × (n − 1) moves. Instead of simulating every second, compute k % (2 × (n − 1)) to find the position within the current cycle.
If the remaining steps are less than n, the ball is still moving forward, so the index equals the remaining steps. Otherwise the ball is on the return path, and the index becomes 2 × (n − 1) − remainingSteps. This converts a potentially large simulation into a constant-time calculation. The solution relies on recognizing the repeating bounce pattern, which is a common trick in math-based problems combined with light simulation reasoning.
Recommended for interviews: Start by explaining the simulation approach because it clearly models the process and proves you understand the mechanics of the problem. Then optimize by identifying the repeating cycle and deriving the mathematical formula. Interviewers typically expect the O(1) pattern-based solution since it demonstrates the ability to convert repetitive simulations into constant-time math.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation | O(k) | O(1) | When constraints are small or when validating logic before optimizing |
| Mathematical Pattern | O(1) | O(1) | Preferred approach when k can be very large and the repeating movement pattern can be derived |