Scale Engineer

Pass the Pillow

Easy
#2362Time: O(time), as the simulation loop runs exactly `time` times.Space: O(1), as we only use a few variables to store the current state, regardless of the input size.1 company
Patterns
Math
Companies
MathWorks

Prompt

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.

  • For example, once the pillow reaches the nth person they pass it to the n - 1th person, then to the n - 2th person and so on.

Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.

 

Example 1:

Input: n = 4, time = 5
Output: 2
Explanation: 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
Explanation: 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

 

Note: This question is the same as 3178: Find the Child Who Has the Ball After K Seconds.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the pillow passing process second by second. We maintain the current position of the pillow and the direction of passing. We iterate time times, updating the pillow's position at each step and reversing the direction when it reaches either end of the line.

Algorithm

  • Initialize a variable currentPerson to 1, representing the person holding the pillow.
  • Initialize a variable direction to 1, representing the forward direction (1 to n).
  • Loop time times, from i = 0 to time - 1.
  • In each iteration, update currentPerson by adding direction to it.
  • After updating, check if the pillow has reached an end of the line:
    • If currentPerson equals n, change direction to -1.
    • If currentPerson equals 1, change direction to 1.
  • After the loop completes, return the final value of currentPerson.

Walkthrough

We can solve this problem by directly simulating the movement of the pillow. We'll need two variables: one to track the current person holding the pillow (currentPerson) and another to track the direction of movement (direction).

Initially, currentPerson is 1, and direction is 1 (indicating forward movement from 1 to n). We then loop time times. In each iteration, we first update the position based on the current direction. After updating, we check if the new position has hit a boundary (1 or n). If it has, we flip the sign of direction to prepare for the next move. After the loop finishes, currentPerson will hold the index of the person with the pillow.

class Solution {    public int passThePillow(int n, int time) {        int currentPerson = 1;        int direction = 1; // 1 for forward, -1 for backward                for (int i = 0; i < time; i++) {            if (currentPerson == n) {                direction = -1;            } else if (currentPerson == 1) {                direction = 1;            }            currentPerson += direction;        }                return currentPerson;    }}

Note: A slight variation is to update the position first and then check the boundaries. The logic remains the same.

class Solution {    public int passThePillow(int n, int time) {        int currentPerson = 1;        int direction = 1; // 1 for forward, -1 for backward                for (int t = 0; t < time; t++) {            currentPerson += direction;            if (currentPerson == n || currentPerson == 1) {                direction *= -1;            }        }                return currentPerson;    }}

Complexity

Time

O(time), as the simulation loop runs exactly `time` times.

Space

O(1), as we only use a few variables to store the current state, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the logic described in the problem statement.

Cons

  • Inefficient for very large values of time, as the runtime is directly proportional to time.

  • Can lead to a 'Time Limit Exceeded' error on platforms with stricter time limits or larger inputs, although it is acceptable for the given constraints.

Solutions

class Solution {public  int passThePillow(int n, int time) {    int ans = 1, k = 1;    while (time-- > 0) {      ans += k;      if (ans == 1 || ans == n) {        k *= -1;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem