# Pass the Pillow
**Difficulty:** EASY
[External](https://leetcode.com/problems/pass-the-pillow)
Canonical: https://scaleengineer.com/dsa/problems/pass-the-pillow
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## Problem
There are `n` people standing in a line labeled from `1` to `n`. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.

* For example, once the pillow reaches the `nth` person they pass it to the `n - 1th` person, then to the `n - 2th` person and so on.

Given the two positive integers `n` and `time`, return _the index of the person holding the pillow after_ `time` _seconds_.

**Example 1:**

**Input:** n = 4, time = 5
**Output:** 2
**Explanation:** People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2.
After five seconds, the 2nd person is holding the pillow.

**Example 2:**

**Input:** n = 3, time = 2
**Output:** 3
**Explanation:** People pass the pillow in the following way: 1 -> 2 -> 3.
After two seconds, the 3rd person is holding the pillow.

**Constraints:**

* `2 <= n <= 1000`
* `1 <= time <= 1000`

**Note:** This question is the same as [ 3178: Find the Child Who Has the Ball After K Seconds.](https://leetcode.com/problems/find-the-child-who-has-the-ball-after-k-seconds/description/)

# Approaches
## Direct Simulation
This approach simulates the pillow passing process second by second. We maintain the current position of the pillow and the direction of passing. We iterate `time` times, updating the pillow's position at each step and reversing the direction when it reaches either end of the line.
**Time:** O(time), as the simulation loop runs exactly `time` times. · **Space:** O(1), as we only use a few variables to store the current state, regardless of the input size.
**Pros:** Simple to understand and implement.; Directly follows the logic described in the problem statement.
**Cons:** Inefficient for very large values of `time`, as the runtime is directly proportional to `time`.; Can lead to a 'Time Limit Exceeded' error on platforms with stricter time limits or larger inputs, although it is acceptable for the given constraints.
### Explanation
We can solve this problem by directly simulating the movement of the pillow. We'll need two variables: one to track the current person holding the pillow (`currentPerson`) and another to track the direction of movement (`direction`).

Initially, `currentPerson` is 1, and `direction` is 1 (indicating forward movement from 1 to n). We then loop `time` times. In each iteration, we first update the position based on the current direction. After updating, we check if the new position has hit a boundary (`1` or `n`). If it has, we flip the sign of `direction` to prepare for the next move. After the loop finishes, `currentPerson` will hold the index of the person with the pillow.

```java
class Solution {
    public int passThePillow(int n, int time) {
        int currentPerson = 1;
        int direction = 1; // 1 for forward, -1 for backward
        
        for (int i = 0; i < time; i++) {
            if (currentPerson == n) {
                direction = -1;
            } else if (currentPerson == 1) {
                direction = 1;
            }
            currentPerson += direction;
        }
        
        return currentPerson;
    }
}
```
*Note: A slight variation is to update the position first and then check the boundaries. The logic remains the same.*
```java
class Solution {
    public int passThePillow(int n, int time) {
        int currentPerson = 1;
        int direction = 1; // 1 for forward, -1 for backward
        
        for (int t = 0; t < time; t++) {
            currentPerson += direction;
            if (currentPerson == n || currentPerson == 1) {
                direction *= -1;
            }
        }
        
        return currentPerson;
    }
}
```
### Algorithm
- Initialize a variable `currentPerson` to 1, representing the person holding the pillow.
- Initialize a variable `direction` to 1, representing the forward direction (1 to n).
- Loop `time` times, from `i = 0` to `time - 1`.
- In each iteration, update `currentPerson` by adding `direction` to it.
- After updating, check if the pillow has reached an end of the line:
  - If `currentPerson` equals `n`, change `direction` to -1.
  - If `currentPerson` equals `1`, change `direction` to 1.
- After the loop completes, return the final value of `currentPerson`.

## Mathematical Calculation using Modulo
This approach avoids the step-by-step simulation by calculating the final position mathematically. It leverages the cyclical nature of the pillow's movement. A full cycle (from person 1 to `n` and back to 1) takes `2 * (n - 1)` seconds. By using modulo arithmetic, we can determine the pillow's position within a single cycle and find the answer in constant time.
**Time:** O(1), as the solution involves a fixed number of arithmetic operations, regardless of the input `n` or `time`. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** Extremely efficient, providing an instant answer.; Scales perfectly to very large values of `n` and `time`.
**Cons:** Requires understanding the underlying pattern of the movement, which might be slightly less intuitive than direct simulation.
### Explanation
The movement of the pillow is periodic. It takes `n - 1` seconds to travel from person 1 to person `n`. It takes another `n - 1` seconds to travel back from person `n` to person 1. Therefore, a complete round trip, or a full cycle, takes `2 * (n - 1)` seconds.

We can use this observation to find a mathematical formula. The key is to determine the direction of movement at the given `time` and the position within that movement.

Let `passLength = n - 1`. This is the duration of a one-way pass.
- The number of full passes completed is `numPasses = time / passLength`.
- The time elapsed in the current pass is `effectiveTime = time % passLength`.

If `numPasses` is even, it means the pillow has completed an even number of passes (e.g., 1->n, then n->1), so it's currently at person 1 and moving forward. The position after `effectiveTime` seconds will be `1 + effectiveTime`.

If `numPasses` is odd, it means the pillow has completed an odd number of passes (e.g., 1->n), so it's currently at person `n` and moving backward. The position after `effectiveTime` seconds will be `n - effectiveTime`.

This method directly computes the result without any loops, making it highly efficient.

```java
class Solution {
    public int passThePillow(int n, int time) {
        int passLength = n - 1;
        int numPasses = time / passLength;
        int effectiveTime = time % passLength;
        
        if (numPasses % 2 == 0) { // Even number of passes -> forward direction
            return 1 + effectiveTime;
        } else { // Odd number of passes -> backward direction
            return n - effectiveTime;
        }
    }
}
```
### Algorithm
- Calculate the number of seconds it takes for the pillow to travel from one end of the line to the other. This is `passLength = n - 1`.
- Determine the number of full passes completed within the given `time`. This is `numPasses = time / passLength`.
- Determine the remaining time, which corresponds to the position within the current pass. This is `effectiveTime = time % passLength`.
- Check if `numPasses` is even or odd to determine the direction of movement.
  - If `numPasses` is even, the pillow is moving forward (from 1 to `n`). The position is `1 + effectiveTime`.
  - If `numPasses` is odd, the pillow is moving backward (from `n` to 1). The position is `n - effectiveTime`.
- Return the calculated position.

# Solutions
### Java

```java
class Solution {
public
  int passThePillow(int n, int time) {
    int ans = 1, k = 1;
    while (time-- > 0) {
      ans += k;
      if (ans == 1 || ans == n) {
        k *= -1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int passThePillow(int n, int time) {
    int ans = 1, k = 1;
    while (time--) {
      ans += k;
      if (ans == 1 || ans == n) {
        k *= -1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def passThePillow(self, n: int, time: int) -> int: ans = k = 1 for _ in range(time): ans += k if ans == 1 or ans == n: k *= - 1 return ans

```