Watch 10 video solutions for Pass the Pillow, a easy level problem involving Math, Simulation. This walkthrough by codestorywithMIK has 5,141 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 <= 10001 <= time <= 1000
Note: This question is the same as 3178: Find the Child Who Has the Ball After K Seconds.
Problem Overview: n people stand in a line and pass a pillow every second. The pillow moves left to right until it reaches the last person, then reverses direction. Given time, determine which person holds the pillow after exactly that many seconds.
Approach 1: Simulate the Passage of Pillow (O(time) time, O(1) space)
This approach directly models the process. Start with person 1 holding the pillow and track the direction of movement using a variable (either +1 or -1). For each second, move the pillow to the next person by adding the direction value. When the current holder becomes 1 or n, flip the direction to simulate the bounce at the ends of the line. The algorithm performs a simple iteration for time steps and updates the position each time. This method mirrors the real behavior of the game and is easy to implement using basic simulation.
Approach 2: Calculate the Final Position using Modulo Arithmetic (O(1) time, O(1) space)
The movement follows a repeating pattern. Passing from person 1 to n takes n-1 steps, and returning from n back to 1 takes another n-1. This creates a cycle of length 2 * (n - 1). Instead of simulating every second, compute time % (2 * (n - 1)) to find the position within the current cycle. If the remainder is less than n, the pillow is still moving forward and the holder is 1 + remainder. Otherwise, the pillow is moving backward and the holder becomes n - (remainder - (n - 1)). This converts the bouncing motion into simple arithmetic using math patterns and avoids iteration entirely.
Recommended for interviews: The modulo arithmetic approach is what interviewers typically expect because it reduces the simulation to constant time. Showing the simulation first demonstrates that you understand the mechanics of the problem. Recognizing the repeating cycle and converting it into a mathematical formula shows stronger problem-solving skills and pattern recognition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate the Passage of Pillow | O(time) | O(1) | Good for understanding the mechanics or when time is small |
| Modulo Arithmetic Cycle Calculation | O(1) | O(1) | Preferred for large time values and interview-optimized solutions |