Intuition

To understand how the pillow moves among the people in line, let's understand the pattern of its movement. The pillow completes a full round when it travels from the first person to the last or vice versa. Each complete round takes $n - 1$ seconds, where n is the total number of people.

To determine how many complete rounds the pillow makes within a given time time, we divide $time$ by $n - 1$. This gives us $fullRounds$, representing the number of times the pillow moves from one end of the line to the other. The remainder of this division, $extraTime = time % (n - 1)$, indicates the extra time left after completing these full rounds.

Now, let's consider the direction of the pillow's movement:

• If $fullRounds$ is even, the pillow moves forward along the line.
• If $fullRounds$ is odd, the pillow moves backward. This directional change occurs after each complete round. In the case of forward movement ($fullRounds$ is even), the person holding the pillow after the extra time will be positioned at $extraTime + 1$ (since we start counting positions from one). Conversely, during backward movement ($fullRounds$ is odd), the person holding the pillow will be at position $n - extraTime$.

Complexity

• Time complexity: $O(1)$.

• Space complexity: $O(1)$.

Solution

Rust

impl Solution {
    pub fn pass_the_pillow(n: i32, time: i32) -> i32 {
        let full_rounds = time / (n - 1);
        let extra_time = time % (n - 1);
        if full_rounds & 1 == 0 {
            extra_time + 1
        } else {
            n - extra_time
        }
    }
}