#2582

Easy

LeetCode Problem Workspace

Pass the Pillow

Pass the Pillow simulates the process of passing an item through a line of people, adjusting the direction based on time.

math simulation

Problem Statement

In a line of n people numbered from 1 to n, the first person starts by holding a pillow. Every second, the current holder passes the pillow to the next person in line. When the pillow reaches the last person, it changes direction and starts passing in the opposite direction.

Given two integers n (the number of people) and time (the number of seconds), your task is to find the index of the person who holds the pillow after the given time seconds.

Examples

Example 1

Input: n = 4, time = 5

Output: 2

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

People pass the pillow in the following way: 1 -> 2 -> 3. After two seconds, the 3rd person is holding the pillow.

Constraints

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

Solution Approach

Simulate the process directly

The problem can be solved by simulating the pillow passing process, keeping track of the current holder and the direction. The direction will reverse when the pillow reaches either end of the line.

Optimize using mathematical properties

Instead of simulating every second, we can mathematically reduce the number of operations by observing the repeating pattern that occurs due to the back-and-forth nature of the pillow passing.

Use modulo arithmetic

You can calculate the position directly by using modulo arithmetic to account for the cycle of passing the pillow back and forth. This avoids unnecessary simulation steps.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

The time complexity is O(1) because the solution only requires a few mathematical operations, and the space complexity is O(1) as no additional data structures are used.

What Interviewers Usually Probe

Understanding of simulating a process with changing directions
Familiarity with mathematical optimizations like modulo arithmetic
Ability to optimize space and time complexities in straightforward problems

Common Pitfalls or Variants

Common pitfalls

Failing to account for the direction change when the pillow reaches the last person
Overcomplicating the problem by simulating each second individually instead of leveraging patterns
Not considering edge cases like the smallest or largest possible values of n and time

Follow-up variants

What if the number of people n is extremely large?
How would the solution change if the pillow direction was more complex (e.g., alternating multiple directions)?
Can the solution be extended to handle a larger set of operations besides just passing the pillow?

FAQ

How does the direction change in the Pass the Pillow problem?

The direction of the pillow changes every time it reaches the last person in the line. After that, the pillow passes in the opposite direction.

What is the optimal way to solve Pass the Pillow?

The optimal solution uses modulo arithmetic to determine the final position, rather than simulating each second individually.

Why does the Pass the Pillow problem involve both Math and Simulation?

This problem requires simulating the passing process while also leveraging mathematical patterns to optimize the solution.

How can I optimize my solution for large values of n or time?

By recognizing the cyclical nature of the pillow passing process and using modulo arithmetic, you can calculate the result in constant time.

What are the time and space complexities for Pass the Pillow?

The time complexity is O(1), and the space complexity is O(1), as no additional data structures are needed for the solution.

terminal

Solution

Solution 1: Simulation

We can simulate the process of passing the pillow, and each time the pillow is passed, if the pillow reaches the front or the end of the queue, the direction of the pillow will change, and the queue will continue to pass the pillow along the opposite direction.

1

2

3

4

5

6

7

8

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        ans = k = 1
        for _ in range(time):
            ans += k
            if ans == 1 or ans == n:
                k *= -1
        return ans

Solution 2: Math

We notice that there are $n - 1$ passes in each round. Therefore, we can divide $time$ by $n - 1$ to get the number of rounds $k$ that the pillow is passed, and then take the remainder of $time$ modulo $n - 1$ to get the remaining passes $mod$ in the current round.

1

2

3

4

5

6

7

8

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        ans = k = 1
        for _ in range(time):
            ans += k
            if ans == 1 or ans == n:
                k *= -1
        return ans

Continue Practicing

#2549 count distinct numbers on board #2507 smallest value after replacing with sum of prime factors #2739 total distance traveled