Find the Child Who Has the Ball After K Seconds

Easy
983.

Find the Child Who Has the Ball After K Seconds

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var numberOfChild = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Find the Child Who Has the Ball After K Seconds

  1. Hint 1

    The ball's path repeats: down the queue and back again.

  2. Hint 2

    One full cycle takes 2 · (n - 1) seconds.

  3. Hint 3

    Reduce k modulo 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

  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

Java

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.

All 337 math problems · the whole catalogue