# Find the Child Who Has the Ball After K Seconds
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-child-who-has-the-ball-after-k-seconds)
Canonical: https://scaleengineer.com/dsa/problems/find-the-child-who-has-the-ball-after-k-seconds
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda)
---
## Problem
You are given two **positive** integers `n` and `k`. There are `n` children numbered from `0` to `n - 1` standing in a queue _in order_ from left to right.

Initially, child 0 holds a ball and the direction of passing the ball is towards the right direction. After each second, the child holding the ball passes it to the child next to them. Once the ball reaches **either** end of the line, i.e. child 0 or child `n - 1`, the direction of passing is **reversed**.

Return the number of the child who receives the ball after `k` seconds.

**Example 1:**

**Input:** n = 3, k = 5

**Output:** 1

**Explanation:**

| Time elapsed | Children    |
| ------------ | ----------- |
| 0            | \[0, 1, 2\] |
| 1            | \[0, 1, 2\] |
| 2            | \[0, 1, 2\] |
| 3            | \[0, 1, 2\] |
| 4            | \[0, 1, 2\] |
| 5            | \[0, 1, 2\] |

**Example 2:**

**Input:** n = 5, k = 6

**Output:** 2

**Explanation:**

| Time elapsed | Children          |
| ------------ | ----------------- |
| 0            | \[0, 1, 2, 3, 4\] |
| 1            | \[0, 1, 2, 3, 4\] |
| 2            | \[0, 1, 2, 3, 4\] |
| 3            | \[0, 1, 2, 3, 4\] |
| 4            | \[0, 1, 2, 3, 4\] |
| 5            | \[0, 1, 2, 3, 4\] |
| 6            | \[0, 1, 2, 3, 4\] |

**Example 3:**

**Input:** n = 4, k = 2

**Output:** 2

**Explanation:**

| Time elapsed | Children       |
| ------------ | -------------- |
| 0            | \[0, 1, 2, 3\] |
| 1            | \[0, 1, 2, 3\] |
| 2            | \[0, 1, 2, 3\] |

**Constraints:**

* `2 <= n <= 50`
* `1 <= k <= 50`

**Note:** This question is the same as [ 2582: Pass the Pillow.](https://leetcode.com/problems/pass-the-pillow/description/)

# Approaches
## Direct Simulation
This approach mimics the ball-passing process step-by-step. We keep track of the ball's current position and its direction of movement. By iterating `k` times, we simulate each second of the process, updating the ball's location and reversing its direction when it reaches either end of the line. This method is intuitive and easy to follow, directly translating the problem's description into code.
**Time:** O(k) - The main part of the algorithm is a loop that runs `k` times, with constant time operations inside each iteration. · **Space:** O(1) - The algorithm uses a fixed number of variables (`currentChild`, `direction`, `time`), regardless of the input size.
**Pros:** Simple to understand and implement.; Works correctly for the given problem constraints.
**Cons:** Inefficient for very large values of `k`, as its runtime is directly proportional to `k`.
### Explanation
We can solve this problem by simulating the movement of the ball for `k` seconds.

- We'll use a variable `currentChild` to track the index of the child with the ball, starting at `0`.
- Another variable, `direction`, will keep track of the movement direction (`1` for right, `-1` for left), starting at `1`.
- We then loop `k` times. In each iteration, representing one pass:
    1. We update `currentChild` by adding the `direction`. This simulates the pass.
    2. After the pass, we check if the ball has landed on an endpoint (`0` or `n-1`).
    3. If it has, we reverse the `direction` for the subsequent passes by multiplying it by `-1`.

After `k` iterations, the value of `currentChild` is the final answer.

```java
class Solution {
    public int findTheChild(int n, int k) {
        int currentChild = 0;
        int direction = 1; // 1 for right, -1 for left

        for (int time = 0; time < k; time++) {
            currentChild += direction;
            if (currentChild == 0 || currentChild == n - 1) {
                direction *= -1;
            }
        }
        return currentChild;
    }
}
```
### Algorithm
- Initialize `currentChild = 0` and `direction = 1` (1 for right, -1 for left).
- Loop `k` times to simulate `k` passes of the ball.
- In each iteration, update the position by one step: `currentChild += direction`.
- After updating, check if the new position is an endpoint (`0` or `n-1`).
- If it is, reverse the direction for the next pass: `direction *= -1`.
- After the loop completes, return the final `currentChild`.

## Mathematical O(1) Solution
This highly efficient approach avoids simulation by using mathematical properties of the ball's movement. The ball's path is periodic. A full round trip from child 0 to `n-1` and back to 0 takes a fixed number of steps. By calculating the total time for one cycle, we can use the modulo operator to find where in the cycle the ball will be after `k` seconds. This allows for a direct calculation of the final position in constant time.
**Time:** O(1) - The solution consists of a few arithmetic calculations that are independent of the input values `n` and `k`. · **Space:** O(1) - The algorithm uses a constant amount of extra space for variables.
**Pros:** Extremely efficient with a constant time complexity, making it suitable for very large `k`.; Elegant solution that demonstrates understanding of the problem's underlying pattern.
**Cons:** Slightly more complex to derive the logic compared to a straightforward simulation.
### Explanation
The movement of the ball is cyclical. It travels from child `0` to `n-1` (which takes `n-1` seconds) and then back from `n-1` to `0` (which also takes `n-1` seconds).

- A complete round trip, therefore, takes `(n-1) + (n-1) = 2 * (n-1)` seconds.
- We can determine the final position by figuring out where in this cycle the `k`-th second falls. The length of one full cycle is `period = 2 * (n - 1)`.
- We can find the effective time within a single cycle using the modulo operator: `effectiveTime = k % period`.
- Now, we analyze the position based on `effectiveTime`:
    - **Forward Pass:** If `effectiveTime` is less than or equal to `n-1`, the ball is still on its way from `0` to `n-1`. In this case, its position is simply `effectiveTime`.
    - **Backward Pass:** If `effectiveTime` is greater than `n-1`, the ball has reached child `n-1` and is on its way back. It reached `n-1` at time `n-1` (within the cycle) and has been moving back for `effectiveTime - (n-1)` seconds. So, its position is `(n-1) - (effectiveTime - (n-1))`.

```java
class Solution {
    public int findTheChild(int n, int k) {
        // The time for a full round trip (0 -> n-1 -> 0) is 2 * (n - 1) seconds.
        int period = 2 * (n - 1);

        // We only need to consider the position within the last, incomplete round trip.
        int effectiveTime = k % period;

        // If the effective time is less than or equal to the time to reach the end (n - 1),
        // the ball is moving forward from 0. The position is equal to the time elapsed.
        if (effectiveTime <= n - 1) {
            return effectiveTime;
        } else {
            // Otherwise, the ball is moving backward from n - 1.
            // It reached n-1 at time (n-1) and is now moving back.
            // The number of steps back from n-1 is (effectiveTime - (n-1)).
            return (n - 1) - (effectiveTime - (n - 1));
        }
    }
}
```
### Algorithm
- Calculate the time for one full round trip (from `0` to `n-1` and back to `0`): `period = 2 * (n - 1)`.
- Calculate the effective time within a single cycle using the modulo operator: `effectiveTime = k % period`.
- Determine if the ball is in the forward or backward part of its journey:
    - If `effectiveTime <= n - 1`, the ball is moving from left to right. Its position is `effectiveTime`.
    - If `effectiveTime > n - 1`, the ball is moving from right to left. Its position is `(n - 1) - (effectiveTime - (n - 1))`.
- Return the calculated position.

# Solutions
### Java

```java
class Solution {
public
  int numberOfChild(int n, int k) {
    int mod = k % (n - 1);
    k /= (n - 1);
    return k % 2 == 1 ? n - mod - 1 : mod;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfChild(int n, int k) {
    int mod = k % (n - 1);
    k /= (n - 1);
    return k % 2 == 1 ? n - mod - 1 : mod;
  }
};

```

### Python

```python
class Solution:
    def numberOfChild(self, n: int, k: int) -> int: k, mod = divmod(k, n - 1) return n - mod - 1 if k & 1 else mod

```