Get started

Find the Child Who Has the Ball After K Seconds — Easy Problem & Solution

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.

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

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

  1. Let cycle = 2 · (n - 1) and at = k mod cycle.
  2. If at < n, the ball is on the outward leg and the answer is at.
  3. 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), not 2n — the endpoints are not visited twice in a row.
  • At at == n - 1 the 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 - 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue