LeetCode 3178 - Find the Child Who Has the Ball After K Seconds

LeetCode Problem 3178

Difficulty: 🟢 Easy
Topics: Math, Simulation

Solution

Problem Understanding

The problem asks us to simulate a game in which n children, numbered from 0 to n - 1, stand in a straight line. Child 0 starts with a ball, and every second the child holding the ball passes it to the next child in the current direction. The direction is initially to the right, and it reverses whenever the ball reaches either end of the line (child 0 or child n - 1).

The inputs are two integers: n, the number of children, and k, the number of seconds that elapse. The output is the index of the child who has the ball after exactly k seconds.

Constraints specify that 2 <= n <= 50 and 1 <= k <= 50. This means the input sizes are small, so a simulation approach will not be inefficient. Edge cases to consider include when the ball is passed exactly at the ends multiple times or when k is small compared to n, as these could lead to off-by-one errors in direction reversal.

Approaches

A brute-force approach involves simulating the ball passing process second by second. Start with child 0 holding the ball and a direction variable set to 1 (right). For each second, update the current child by adding the direction. If the ball reaches the first or last child, reverse the direction. This approach is guaranteed to work because it exactly mimics the process, but it is linear in k, which is acceptable given the constraints.

The optimal approach leverages the observation that the ball follows a repeating zig-zag pattern along the line. If we imagine the children as indices 0 to n - 1, the ball's movement can be considered along a “virtual line” that extends and reflects at the ends. After k seconds, the ball is at position k mod (2*(n-1)) along this virtual line. If the position is greater than or equal to n, we reflect it back to get the actual index. This approach avoids simulating each second, computing the result in constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k)	O(1)	Simulates each second; simple but linear in k
Optimal	O(1)	O(1)	Uses modulo and reflection to compute final position

Algorithm Walkthrough

1. Compute the cycle length as 2 * (n - 1). This represents a full round trip from child 0 to child n-1 and back to 0.
2. Compute the effective position along this virtual line as k % cycle_length. This gives the ball’s position in the current cycle.
3. If the effective position is less than n, the ball is still moving to the right, so the current index is the effective position itself.
4. If the effective position is greater than or equal to n, the ball is moving left after reflecting at the end. Compute the actual index as 2*(n-1) - effective_position.
5. Return the computed index as the child who holds the ball.

Why it works: The ball moves in a predictable, repeating pattern. By computing the position modulo the full cycle length and reflecting when necessary, we directly obtain the ball's index without simulating each second.

Python Solution

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

The code first calculates the full cycle of movement and the position of the ball within that cycle. If the position is within the first pass to the right, it returns that position. If the position is on the return path, it reflects the index back to the left.

Go Solution

func numberOfChild(n int, k int) int {
    cycle := 2 * (n - 1)
    pos := k % cycle
    if pos < n {
        return pos
    }
    return cycle - pos
}

The Go implementation mirrors the Python version. No special handling for slices or pointers is needed because the algorithm only uses integers. Reflection is computed using the same formula.

Worked Examples

Example 1: n = 3, k = 5

Cycle length = 2 * (3 - 1) = 4

Effective position = 5 % 4 = 1

Since 1 < 3, result = 1

Example 2: n = 5, k = 6

Cycle length = 2 * (5 - 1) = 8

Effective position = 6 % 8 = 6

Since 6 >= 5, result = 8 - 6 = 2

Example 3: n = 4, k = 2

Cycle length = 2 * (4 - 1) = 6

Effective position = 2 % 6 = 2

Since 2 < 4, result = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only arithmetic operations and a conditional check are performed
Space	O(1)	Only a few integer variables are used

The optimal solution is constant time and space, leveraging the repeating pattern of ball passing.

Test Cases

# provided examples
assert Solution().numberOfChild(3, 5) == 1  # zig-zag pattern leads to child 1
assert Solution().numberOfChild(5, 6) == 2  # after 6 passes, child 2 has the ball
assert Solution().numberOfChild(4, 2) == 2  # ball moves 2 steps to the right

# edge cases
assert Solution().numberOfChild(2, 1) == 1  # smallest n, ball passes to second child
assert Solution().numberOfChild(2, 2) == 0  # returns to first child
assert Solution().numberOfChild(50, 50) == 50 % (2*(50-1))  # large n and k

Test	Why
n=3, k=5	Tests typical zig-zag with small n
n=5, k=6	Tests reflection after reaching end
n=4, k=2	Tests simple forward motion
n=2, k=1	Minimal input, first pass
n=2, k=2	Minimal input, returns to start
n=50, k=50	Tests upper bounds of constraints

Edge Cases

One important edge case is the smallest line n=2. The ball immediately reverses after each pass, and it is essential to correctly handle the reflection. Another edge case occurs when k is exactly a multiple of the cycle length; the ball returns to the start, and failing to compute modulo correctly could produce an off-by-one error. A final edge case is when k is slightly larger than the cycle length, requiring proper reflection to determine the correct child without simulating every second. The solution handles all these correctly using the modulo and reflection approach.