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 <= 1000Note: This question is the same as 3178: Find the Child Who Has the Ball After K Seconds.
In #2582 Pass the Pillow, n people stand in a line and pass a pillow every second. The direction reverses whenever the pillow reaches either end of the line. A direct way to reason about the problem is to simulate the passing process, updating the current position and switching direction when reaching person 1 or n. While simple, this approach takes O(time) steps.
A more efficient strategy uses a mathematical observation. Passing the pillow from one end to the other and back forms a repeating cycle of length 2 × (n − 1). Instead of simulating every step, we can reduce the time using a modulus operation with the cycle length and determine whether the pillow is currently moving forward or backward. This insight allows us to compute the final position directly in constant time.
The optimized method therefore achieves O(1) time and O(1) space, making it ideal for large values of time.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Step-by-step Simulation | O(time) | O(1) |
| Mathematical Cycle Observation | O(1) | O(1) |
Aryan Mittal
Use these hints if you're stuck. Try solving on your own first.
Maintain two integer variables, direction and i, where direction denotes the current direction in which the pillow should pass, and i denotes an index of the person holding the pillow.
While time is positive, update the current index with the current direction. If the index reaches the end of the line, multiply direction by - 1.
This approach involves simulating the process of passing the pillow using a loop. We start from the first person in the line and traverse it based on the time parameter. When we reach the end, we simply reverse the direction and continue until the given time is exhausted.
Time Complexity: O(time), since we simulate each passing of the pillow individually.
Space Complexity: O(1), as we only utilize a few integer variables for tracking state.
1function passThePillow(n, time) {
2 let position = 1;
3 let direction = 1;
4
5 for (let t
This JavaScript implementation uses a simple for-loop to determine changes in the pillow's position, adjusting the direction of movement when the bounds are met.
This approach employs modulo arithmetic to determine the position of the pillow. By calculating the rounds of back-and-forth transfers based on time, we can derive the final position without directly simulating each second.
Time Complexity: O(1)
Space Complexity: O(1)
1public
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems like Pass the Pillow may appear in interviews as warm-up or logic-based questions. They test pattern recognition, mathematical reasoning, and the ability to optimize simulations.
Yes, you can simulate each second of passing and change direction at the ends of the line. However, this approach takes O(time) steps and is less efficient than the mathematical cycle-based solution.
The optimal approach uses a mathematical observation about the repeating passing pattern. The pillow movement forms a cycle of length 2 × (n − 1), so using modulus with the time value allows us to determine the final holder in constant time.
No complex data structure is required for this problem. Since the pattern repeats predictably, simple arithmetic and variables are enough to compute the final position efficiently.
This Java solution applies modular arithmetic to deduce the final position of the pillow, opting to calculate rather than simulate each sequential step.