Pass the Pillow

Difficulty: Easy | Acceptance: 56.50% | Paid: No Topics: Math, Simulation

There are n people standing in a line labeled from 1 to n. The first person in line is holding a pillow initially.

Every second, the person holding the pillow passes it to the next person standing in line. Once the pillow reaches the end of the line (i.e., the nth person), the passing direction reverses, and the pillow continues to be passed in the opposite direction.

Given the number of people in the line n and the time time in seconds, return the index of the person holding the pillow after time seconds.

• Examples
• Constraints
• Simulation Approach
• Mathematical Approach

Examples

Example 1:

Input: n = 4, time = 5
Output: 2
Explanation: People are labeled as 1, 2, 3, 4. The pillow passing sequence is: 1->2->3->4->3->2. After 5 seconds, the pillow is at person 2.

Example 2:

Input: n = 3, time = 2
Output: 3
Explanation: People are labeled as 1, 2, 3. The pillow passing sequence is: 1->2->3. After 2 seconds, the pillow is at person 3.

Constraints

2 <= n <= 1000
1 <= time <= 1000

Simulation Approach

Intuition Simulate the pillow passing process second by second, tracking the current position and direction of movement.

Steps

• Start at position 1 with forward direction
• For each second, move the pillow in the current direction
• Reverse direction when reaching person 1 or person n
• Return the final position after time seconds

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        pos = 1
        direction = 1  # 1 for forward, -1 for backward
        
        for _ in range(time):
            pos += direction
            if pos == n:
                direction = -1
            elif pos == 1:
                direction = 1
        
        return pos

Complexity

• Time: O(time)
• Space: O(1)
• Notes: Simple and intuitive, but not optimal for large time values

Mathematical Approach

Intuition The pillow moves in a repeating cycle of length 2(n-1). Use modulo arithmetic to find the position directly without simulation.

Steps

• Calculate the cycle length as 2(n-1)
• Find the remainder when time is divided by cycle length
• If remainder is in the first half (≤ n-1), position is 1 + remainder
• Otherwise, position is n - (remainder - (n-1))

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        cycle = 2 * (n - 1)
        remainder = time % cycle
        
        if remainder <= n - 1:
            return 1 + remainder
        else:
            return n - (remainder - (n - 1))

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Optimal solution using mathematical pattern recognition