Find the Child Who Has the Ball After K Seconds — Solution
Find the Child Who Has the Ball After K Seconds solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Child Who Has the Ball After K Seconds is an easy coding problem on math and simulation, asked in Amazon, Google and Cognizant interviews.
- Difficulty: Easy
- Topics: Math, Simulation
- Asked at: Amazon, Google, Cognizant
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
n children stand in a queue numbered 0 … n - 1. Child 0 starts with a ball, and every second it passes to the next child in the current direction. When it reaches either end the direction reverses.
Return the number of the child holding the ball after exactly k seconds.
Example 1
Input: n = 3, k = 5
Output: 1
Explanation: 0 → 1 → 2 → 1 → 0 → 1.
Example 2
Input: n = 5, k = 6
Output: 2
Explanation: The ball reaches child 4 at second 4 and turns back.
Example 3
Input: n = 4, k = 2
Output: 2
Constraints
2 <= n <= 501 <= k <= 50
Hints for Find the Child Who Has the Ball After K Seconds
Hint 1
The ball's path repeats: down the queue and back again.
Hint 2
One full cycle takes
2 · (n - 1)seconds.Hint 3
Reduce
kmodulo that cycle, then fold the position back if it has passed the end.
How to solve Find the Child Who Has the Ball After K Seconds
The motion is a bounce with period 2 · (n - 1). Reduce k modulo the period; a position below n is the answer directly, and anything beyond is mirrored back.
Approach
- Let
cycle = 2 · (n - 1)andat = k mod cycle. - If
at < n, the ball is on the outward leg and the answer isat. - Otherwise it is on the return leg, at
cycle - at.
Why it works
The outward leg takes n - 1 seconds and the return leg the same, so the position is a triangle wave — which is exactly what the modulus plus the fold reproduces. Simulating second by second gives the same answer and is fine at k <= 50, but the closed form holds for any k.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- The cycle is
2 · (n - 1), not2n— the endpoints are not visited twice in a row. - At
at == n - 1the ball is exactly at the far end, which the first branch already covers. n >= 2, so the cycle is never zero.
Reference solution
Python
def numberOfChild(n: int, k: int) -> int:
cycle = 2 * (n - 1)
at = k % cycle
return at if at < n else cycle - atJava
public static int numberOfChild(int n, int k) {
int cycle = 2 * (n - 1);
int at = k % cycle;
return at < n ? at : cycle - at;
}C++
int numberOfChild(int n, int k) {
int cycle = 2 * (n - 1);
int at = k % cycle;
return at < n ? at : cycle - at;
}JavaScript
var numberOfChild = function(n, k) {
var cycle = 2 * (n - 1);
var at = k % cycle;
return at < n ? at : cycle - at;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.