Skip to main content
Talentd

Find the Child Who Has the Ball After K Seconds - Solution & Explanation

EasyMathSimulation17 min readAsked at: Agoda
Practice this problem

Problem Statement

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 <= 50
  • 1 <= k <= 50

 

Note: This question is the same as 2582: Pass the Pillow.

Approach Overview

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 1: Simulation Approach

This approach involves simulating the process of passing the ball step by step. We iterate from 0 to k and update the position of the child holding the ball at each second. We keep track of the direction: moving right initially and reversing the direction upon reaching either end of the line. This direct simulation helps in understanding the movement of the ball clearly.

This C program initializes direction as 1 to indicate a rightward movement. We use a loop to simulate the passing of the ball for k seconds, updating the currentChild index. If the ball reaches either end, the direction is reversed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(k) because we iterate k times.
Space Complexity: O(1) since we use a constant amount of extra space.

Try this approach in the editor →

Approach 2: Mathematical Pattern Approach

This approach utilizes a mathematical insight based on movement patterns. Notice that as the ball is passed, if it reaches the end, the direction reverses. Given the small constraints, a pattern emerges in how children are passed the ball. By simulating this until a repetition, we can calculate the final position significantly faster without iterating through each second.

The C program uses a modulus operation to predictably shorten the repetition of direction changes so that we iterate for k % (2 * (n - 1)) seconds. This simplifies the calculation significantly. We handle direction similarly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(k % (2 * (n - 1)))
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Mathematics

We notice that there are n - 1 passes in each round. Therefore, we can take k modulo n - 1 to get the number of passes mod in the current round. Then we divide k by n - 1 to get the current round number k.

Next, we judge the current round number k:

  • If k is odd, then the current passing direction is from the end of the queue to the head, so it will be passed to the person with the number n - mod - 1.
  • If k is even, then the current passing direction is from the head of the queue to the end, so it will be passed to the person with the number mod.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulation Approach

Time Complexity: O(k) because we iterate k times.
Space Complexity: O(1) since we use a constant amount of extra space.

Mathematical Pattern Approach

Time Complexity: O(k % (2 * (n - 1)))
Space Complexity: O(1)

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
SimulationO(k)O(1)When constraints are small or when validating logic before optimizing
Mathematical PatternO(1)O(1)Preferred approach when k can be very large and the repeating movement pattern can be derived

Video Solution

3178. Find the Child Who Has the Ball After K Seconds | Math | Cyclic Math Pattern • Aryan Mittal • 2,138 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Child Who Has the Ball After K Seconds easy or hard?
The problem is classified as Easy on LeetCode with an acceptance rate around 60%. The straightforward simulation is simple to implement, while the main insight is recognizing the repeating back-and-forth cycle to reduce the complexity to O(1).
Find the Child Who Has the Ball After K Seconds Python/Java solution
Both Python and Java implementations follow the same idea. The optimized solution computes cycle = 2 * (n - 1), finds remaining = k % cycle, and returns remaining if it is less than n; otherwise it returns cycle - remaining. This produces an O(1) time solution in any language.
How to solve Find the Child Who Has the Ball After K Seconds in O(1)?
Observe that the ball moves forward from index 0 to n−1 and then backward to 0, forming a cycle of length 2 × (n − 1). Compute remaining = k % (2 × (n − 1)). If remaining < n, the answer is remaining; otherwise the ball is moving backward and the index becomes 2 × (n − 1) − remaining. This avoids iterating through each second.
What is the best approach for Find the Child Who Has the Ball After K Seconds?
The optimal approach uses a mathematical pattern instead of simulating every move. The ball's motion repeats every 2 × (n − 1) seconds because it travels from the first child to the last and back. By computing k % (2 × (n − 1)), you determine the position within the cycle and calculate the child index in O(1) time and O(1) space.
Is Find the Child Who Has the Ball After K Seconds asked at Google/Amazon/Meta?
Problems based on bouncing pointers and repeating patterns commonly appear in interviews at companies like Amazon and Google. While this exact problem may vary in wording, the underlying idea of detecting cycles and converting simulations into mathematical formulas is a frequent interview pattern.
What data structure is used in Find the Child Who Has the Ball After K Seconds?
No complex data structure is required. The solution relies on simple integer variables to track the current position and direction for simulation, or modular arithmetic for the optimized mathematical approach. The focus is on pattern recognition rather than data structure manipulation.
What is the time complexity of Find the Child Who Has the Ball After K Seconds?
The simulation approach runs in O(k) time because it updates the ball position one second at a time. The optimized mathematical approach runs in O(1) time by exploiting the repeating movement cycle of length 2 × (n − 1). Both approaches use O(1) additional space.

Ready to solve this problem?

Practice Find the Child Who Has the Ball After K Seconds with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Losers of the Circular Game