Find the Child Who Has the Ball After K Seconds

Difficulty: Easy | Acceptance: 62.10% | Paid: No Topics: Math, Simulation

You are given n children standing in a line. The children are numbered from 0 to n - 1 from left to right. You are also given an integer k.

A ball is being passed between the children. The ball starts at child 0. The ball moves to the right (towards higher indices) one child per second. When the ball reaches the last child (child n - 1), it changes direction and moves to the left one child per second. When the ball reaches the first child (child 0), it changes direction and moves to the right again.

This process continues for k seconds. Return the number of the child who has the ball after k seconds.

• Examples
• Constraints
• Approach 1: Simulation
• Approach 2: Mathematical Modulo

Examples

Example 1

Input: n = 3, k = 2
Output: 2
Explanation:
1. At second 0, the ball is at child 0.
2. At second 1, the ball moves to child 1.
3. At second 2, the ball moves to child 2.
So, the ball is at child 2 after 2 seconds.

Example 2

Input: n = 4, k = 5
Output: 1
Explanation:
1. At second 0, the ball is at child 0.
2. At second 1, the ball moves to child 1.
3. At second 2, the ball moves to child 2.
4. At second 3, the ball moves to child 3.
5. At second 4, the ball changes direction to left and moves to child 2.
6. At second 5, the ball moves to child 1.
So, the ball is at child 1 after 5 seconds.

Example 3

Input: n = 2, k = 4
Output: 0
Explanation:
1. At second 0, the ball is at child 0.
2. At second 1, the ball moves to child 1.
3. At second 2, the ball changes direction to left and moves to child 0.
4. At second 3, the ball changes direction to right and moves to child 1.
5. At second 4, the ball changes direction to left and moves to child 0.
So, the ball is at child 0 after 4 seconds.

Constraints

2 <= n <= 50
1 <= k <= 50

Simulation

Intuition Since the constraints for n and k are very small (up to 50), we can simply simulate the process second by second. We keep track of the current position and the direction of movement.

Steps

• Initialize pos to 0 and direction to 1 (representing right).
• Loop k times:
  • Update pos by adding direction.
  • If pos reaches n - 1, change direction to -1 (left).
  • If pos reaches 0, change direction to 1 (right).
• Return pos.

class Solution:
    def numberOfChild(self, n: int, k: int) -> int:
        pos = 0
        direction = 1
        for _ in range(k):
            pos += direction
            if pos == n - 1:
                direction = -1
            elif pos == 0:
                direction = 1
        return pos

Complexity

• Time: O(k)
• Space: O(1)
• Notes: Simple and easy to implement, suitable for small constraints.

Mathematical Modulo

Intuition The ball moves in a repeating cycle. It goes from 0 to n-1 and back to 0. The length of this cycle is 2 * (n - 1). We can use the modulo operator to find the effective time within one cycle and map it to the child’s position.

Steps

• Calculate the cycle length: cycle = 2 * (n - 1).
• Find the remainder of k divided by cycle: rem = k % cycle.
• If rem is less than or equal to n - 1, the ball is moving right, so the position is rem.
• Otherwise, the ball is moving left. The position is cycle - rem.

class Solution:
    def numberOfChild(self, n: int, k: int) -> int:
        cycle = 2 * (n - 1)
        rem = k % cycle
        if rem <= n - 1:
            return rem
        return cycle - rem

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Optimal solution, handles very large values of k efficiently.