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.

#2582

Easy

auto_awesome数学·结合·模拟

LeetCode 题解工作台

递枕头

n 个人站成一排，按从 1 到 n 编号。最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n -…

数学模拟

题目描述

n 个人站成一排，按从 1 到 n 编号。最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。

给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号。

示例 1：

输入：n = 4, time = 5
输出：2
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。
5 秒后，枕头传递到第 2 个人手中。

示例 2：

输入：n = 3, time = 2
输出：3
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 。
2 秒后，枕头传递到第 3 个人手中。

提示：

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

注意：本题与 3178.找出 K 秒后拿着球的孩子一致。

lightbulb

解题思路

方法一：模拟

我们可以模拟枕头传递的过程，每次传递枕头时，如果枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

时间复杂度 $O(time)$ ，空间复杂度 $O(1)$ 。其中 $time$ 为给定的时间。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	O(1)
空间	O(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2549 统计桌面上的不同数字 #2507 使用质因数之和替换后可以取到的最小值 #2739 总行驶距离