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.
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.
This C solution simulates the passage of the pillow by updating the position with a direction variable to track when the end of the line is reached. Once the last person receives the pillow, the direction is inverted. This continues until 'time' iterations are exhausted.
C++
Java
Python
C#
JavaScript
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.
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.
This C code calculates how many complete cycles of passing are done using time / (n - 1). Depending on whether the cycle count is even or odd, the remainder updates the position in forward or backward direction.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Simulate the Passage of Pillow | Time Complexity: O(time), since we simulate each passing of the pillow individually. |
| Calculate the Final Position using Modulo Arithmetic | Time Complexity: O(1) |
Pass the Pillow || Maths & Logic || Leetcode-2582 • Aryan Mittal • 4,503 views views
Watch 9 more video solutions →Practice Pass the Pillow with our built-in code editor and test cases.
Practice on FleetCode