Pass the Pillow

Problem Description

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. Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.

Key Insights

• The pillow starts with the first person and is passed to the next in line every second.
• The direction of passing reverses when the pillow reaches the last person.
• The pattern can be observed as a sequence of movements that can be calculated mathematically rather than simulating each second.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To determine the index of the person holding the pillow after time seconds, we can use a mathematical approach based on the total number of people n. The pillow will move in a linear path from the first person to the last and then back to the first. The effective position can be calculated using the modulo operation to account for the change in direction.

1. Calculate the total distance traveled in the sequence (2 * n - 2) to account for the round trip.
2. Use time % (2 * n - 2) to find the effective time after completing full cycles.
3. Depending on the resulting index, determine if the pillow is moving forward or backward.

Code Solutions