Find the Child Who Has the Ball After K Seconds solution and explanation
9 more videos on this problem
3178. Find the Child Who Has the Ball After K Seconds | Math | Cyclic Math PatternAryan Mittal · 9:30 · 2K views
3178 Find the Child Who Has the Ball After K Seconds How to 🤔 in Interview || O(N)-O(1) 🔥Ayush Rao · 7:00 · 657 views
A -Find the Child Who Has the Ball After K Seconds | LEETCODE weekly-contest-401 | LEETCODE SOLUTIONJUST CODE · 0:29 · 547 views
Lesson 625/№3178. Find the Child Who Has the Ball After K Seconds / LeetcodeYersham · 12:41 · 335 views
3178. Find the Child Who Has the Ball After K Seconds (Leetcode Easy)Programming Live with Larry · 5:03 · 252 views
Leetcode 3178: Find the Child Who Has the Ball After K SecondsAlgorithms Casts · 12:51 · 211 views
100325 Find the Child Who Has the Ball After K Seconds | leetcode || contest 401 || solved || javaSsquare · 1:10 · 184 views
Find the Child Who Has the Ball After K Seconds | Leetcode Weekly ContestDeveloper Coder · 3:26 · 177 views
LeetCode 3178 | Find the Child Who Has the Ball After K Seconds | Weekly Contest 401 | Math | DSAAlgo Horizon · 4:21 · 135 views
3178. Find the Child Who Has the Ball After K Seconds #leetcodequestionandanswers #java #codingCodeVia · 2:44 · 77 views
The problem
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.
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.
def find_child_after_k_seconds(n, k):
direction = 1
current_child = 0
for _ in range(k):
current_child += direction
if current_child == 0 or current_child == n - 1:
direction *= -1
return current_child
n = 3
k = 5
print(find_child_after_k_seconds(n, k))public class PassThePillow {
public static int findChildAfterKSeconds(int n, int k) {
int direction = 1;
int currentChild = 0;
for (int i = 0; i < k; i++) {
currentChild += direction;
if (currentChild == 0 || currentChild == n - 1) {
direction *= -1;
}
}
return currentChild;
}
public static void main(String[] args) {
int n = 3, k = 5;
System.out.println(findChildAfterKSeconds(n, k));
}
}#include <iostream>
int findChildAfterKSeconds(int n, int k) {
int direction = 1;
int currentChild = 0;
for (int i = 0; i < k; i++) {
currentChild += direction;
if (currentChild == 0 || currentChild == n-1) {
direction *= -1;
}
}
return currentChild;
}
int main() {
int n = 3, k = 5;
std::cout << findChildAfterKSeconds(n, k) << std::endl;
return 0;
}function findChildAfterKSeconds(n, k) {
let direction = 1;
let currentChild = 0;
for (let i = 0; i < k; i++) {
currentChild += direction;
if (currentChild === 0 || currentChild === n - 1) {
direction *= -1;
}
}
return currentChild;
}
let n = 3, k = 5;
console.log(findChildAfterKSeconds(n, k));#include <stdio.h>
int findChildAfterKSeconds(int n, int k) {
int direction = 1; // 1 for right, -1 for left
int currentChild = 0;
for (int i = 0; i < k; i++) {
currentChild += direction;
if (currentChild == 0 || currentChild == n-1) {
direction *= -1; // Reverse direction
}
}
return currentChild;
}
int main() {
int n = 3, k = 5;
printf("%d\n", findChildAfterKSeconds(n, k));
return 0;
}using System;
class Program {
public static int FindChildAfterKSeconds(int n, int k) {
int direction = 1;
int currentChild = 0;
for (int i = 0; i < k; i++) {
currentChild += direction;
if (currentChild == 0 || currentChild == n - 1) {
direction *= -1;
}
}
return currentChild;
}
static void Main() {
int n = 3; int k = 5;
Console.WriteLine(FindChildAfterKSeconds(n, k));
}
}The Python version utilizes a loop to simulate the ball passing every second up to k, modifying current_child based on the current direction, and reversing the direction at the ends.
Time Complexity: O(k)
Space Complexity: O(1)
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.
def find_child_after_k_seconds(n, k):
k = k % (2 * (n - 1)) # Effective length of cycle
direction = 1
current_child = 0
for _ in range(k):
current_child += direction
if current_child == 0 or current_child == n - 1:
direction *= -1
return current_child
n = 3
k = 5
print(find_child_after_k_seconds(n, k))public class PassThePillow {
public static int findChildAfterKSeconds(int n, int k) {
k = k % (2 * (n - 1));
int direction = 1;
int currentChild = 0;
for (int i = 0; i < k; i++) {
currentChild += direction;
if (currentChild == 0 || currentChild == n - 1) {
direction *= -1;
}
}
return currentChild;
}
public static void main(String[] args) {
int n = 3, k = 5;
System.out.println(findChildAfterKSeconds(n, k));
}
}#include <iostream>
int findChildAfterKSeconds(int n, int k) {
k = k % (2 * (n - 1));
int direction = 1;
int currentChild = 0;
for (int i = 0; i < k; i++) {
currentChild += direction;
if (currentChild == 0 || currentChild == n-1) {
direction *= -1;
}
}
return currentChild;
}
int main() {
int n = 3, k = 5;
std::cout << findChildAfterKSeconds(n, k) << std::endl;
return 0;
}function findChildAfterKSeconds(n, k) {
k = k % (2 * (n - 1)); // Simulate effective passes
let direction = 1;
let currentChild = 0;
for (let i = 0; i < k; i++) {
currentChild += direction;
if (currentChild === 0 || currentChild === n - 1) {
direction *= -1;
}
}
return currentChild;
}
let n = 3, k = 5;
console.log(findChildAfterKSeconds(n, k));#include <stdio.h>
int findChildAfterKSeconds(int n, int k) {
k = k % (2 * (n - 1)); // Determine effective passes taking reversals into account
int direction = 1; // Start with right direction
int currentChild = 0;
for (int i = 0; i < k; i++) {
currentChild += direction;
if (currentChild == 0 || currentChild == n-1) {
direction *= -1; // Reverse direction
}
}
return currentChild;
}
int main() {
int n = 3, k = 5;
printf("%d\n", findChildAfterKSeconds(n, k));
return 0;
}using System;
class Program {
public static int FindChildAfterKSeconds(int n, int k) {
k = k % (2 * (n - 1));
int direction = 1;
int currentChild = 0;
for (int i = 0; i < k; i++) {
currentChild += direction;
if (currentChild == 0 || currentChild == n - 1) {
direction *= -1;
}
}
return currentChild;
}
static void Main() {
int n = 3; int k = 5;
Console.WriteLine(FindChildAfterKSeconds(n, k));
}
}Python's solution employs k % (2 * (n - 1)) to determine effective passes, which allows us to determine the eventual holder efficiently.
Time Complexity: O(k % (2 * (n - 1)))
Space Complexity: O(1)
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
kis 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 numbern - mod - 1. - If
kis 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 numbermod.
The time complexity is O(1), and the space complexity is O(1).
function numberOfChild(n: number, k: number): number {
const mod = k % (n - 1);
k = (k / (n - 1)) | 0;
return k % 2 ? n - mod - 1 : mod;
}func numberOfChild(n int, k int) int {
mod := k % (n - 1)
k /= (n - 1)
if k%2 == 1 {
return n - mod - 1
}
return mod
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulation Approach | Time Complexity: O(k) |
| Mathematical Pattern Approach | Time Complexity: O(k % (2 * (n - 1))) |
| Mathematics | – |
Complexity analysis
| 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 |
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.