Problem Description

You have n people standing in a line, numbered from 1 to n. Person 1 starts with a pillow and passes it to the next person every second. When the pillow reaches person n (the last person), the direction reverses - person n passes it back to person n-1, then to person n-2, and so on. When the pillow reaches person 1 again, the direction reverses once more, and the pattern continues.

The pillow moves like a bouncing ball between the two ends of the line:

• Starting at person 1, it moves forward: 1 → 2 → 3 → ... → n
• Upon reaching person n, it bounces back: n → n-1 → n-2 → ... → 1
• Upon reaching person 1, it bounces forward again, and this pattern repeats

Given two positive integers:

• n: the number of people in the line
• time: the number of seconds that have passed

You need to find which person (by their position number) is holding the pillow after exactly time seconds.

For example, if n = 4 and time = 5:

• At time 0: Person 1 has the pillow
• At time 1: Person 2 has the pillow
• At time 2: Person 3 has the pillow
• At time 3: Person 4 has the pillow (reaches the end, direction reverses)
• At time 4: Person 3 has the pillow
• At time 5: Person 2 has the pillow

The answer would be 2.

Intuition

The key observation is that the pillow moves in a predictable pattern - it bounces back and forth between position 1 and position n. We can think of this as a person walking along a line, taking one step each second, and turning around whenever they reach either end.

To track this movement, we need two pieces of information:

1. The current position of the pillow holder
2. The direction the pillow is moving (forward towards n or backward towards 1)

We can simulate this step-by-step process:

• Start at position 1 with the pillow moving forward (direction = +1)
• For each second that passes, move one position in the current direction
• Whenever we reach an endpoint (position 1 or position n), we reverse the direction

The direction can be represented as a variable k that is either +1 (moving forward) or -1 (moving backward). When we hit a boundary, we simply multiply k by -1 to flip the direction.

For example, if we're at position n and moving forward (k = 1), we've hit the right boundary. We change k to -1, so the next move will be n + (-1) = n - 1, moving backward.

By simulating exactly time steps of this process, we can determine the final position of the pillow. The simulation directly mirrors the physical process described in the problem, making it an intuitive and straightforward approach.

Learn more about Math patterns.

Solution Approach

The simulation approach implements the intuition directly by tracking the pillow's position and direction through each second.

Implementation Steps:

1. Initialize variables:

   • ans = 1: The current position of the pillow holder (starts at person 1)
   • k = 1: The direction of movement (+1 for forward, -1 for backward)

2. Simulate each second:

   • Loop time times to simulate each passing second
   • In each iteration:
     • Move the pillow: ans += k (add the direction to current position)
     • Check if we've hit a boundary: if ans == 1 or ans == n
     • If at a boundary, reverse direction: k *= -1

3. Return the final position after all time seconds have passed

Why the boundary check happens after moving: Notice that we update the position first (ans += k) and then check for boundaries. This is because:

• When we reach position n moving forward, the next move should be backward
• When we reach position 1 moving backward, the next move should be forward
• The direction change takes effect for the next move, not the current one

Example walkthrough with n = 4, time = 5:

• Start: ans = 1, k = 1
• Second 1: ans = 1 + 1 = 2, no boundary hit
• Second 2: ans = 2 + 1 = 3, no boundary hit
• Second 3: ans = 3 + 1 = 4, boundary hit! Set k = -1
• Second 4: ans = 4 + (-1) = 3, no boundary hit
• Second 5: ans = 3 + (-1) = 2, no boundary hit
• Return: 2

The time complexity is O(time) since we iterate exactly time times, and the space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's trace through the solution with n = 3 people and time = 4 seconds.

Initial Setup:

• ans = 1 (pillow starts at person 1)
• k = 1 (moving forward towards person n)

Simulation:

Second 1:

• Move pillow: ans = ans + k = 1 + 1 = 2
• Check boundaries: ans ≠ 1 and ans ≠ 3, no boundary hit
• State: Person 2 has the pillow, still moving forward

Second 2:

• Move pillow: ans = ans + k = 2 + 1 = 3
• Check boundaries: ans = 3 (hit right boundary!)
• Reverse direction: k = k × (-1) = -1
• State: Person 3 has the pillow, will move backward next

Second 3:

• Move pillow: ans = ans + k = 3 + (-1) = 2
• Check boundaries: ans ≠ 1 and ans ≠ 3, no boundary hit
• State: Person 2 has the pillow, moving backward

Second 4:

• Move pillow: ans = ans + k = 2 + (-1) = 1
• Check boundaries: ans = 1 (hit left boundary!)
• Reverse direction: k = k × (-1) = 1
• State: Person 1 has the pillow, will move forward next

Result: After 4 seconds, person 1 is holding the pillow.

The pillow's journey: 1 → 2 → 3 → 2 → 1

This demonstrates how the pillow bounces between the endpoints, with direction changes occurring exactly when we reach person 1 or person n.

Solution Implementation

Time and Space Complexity

The time complexity is O(time) because the code contains a single for loop that iterates exactly time times. In each iteration, the code performs constant-time operations: adding to ans, checking conditions with an if statement, and potentially multiplying k by -1. Since these operations are all O(1) and they are executed time times, the overall time complexity is O(time).

The space complexity is O(1) because the code only uses a fixed amount of extra space regardless of the input size. The variables ans and k are simple integers that do not scale with the input parameters n or time. No additional data structures like arrays, lists, or recursive call stacks are used, so the space usage remains constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-one error in boundary checking

A common mistake is checking boundaries before updating the position, or using incorrect boundary conditions:

Incorrect approach:

# Wrong: Checking boundary BEFORE moving
for _ in range(time):
    if current_position == 1 or current_position == n:
        direction *= -1
    current_position += direction  # This will overshoot!

This causes the pillow to go beyond the boundaries (position 0 or n+1) because the direction changes before the move is made.

Solution: Always update position first, then check if the new position is at a boundary:

for _ in range(time):
    current_position += direction
    if current_position == 1 or current_position == n:
        direction *= -1

2. Incorrect cycle length calculation in optimized solution

When calculating the cycle pattern, a frequent error is using n * 2 instead of (n - 1) * 2:

Incorrect:

cycle_length = n * 2  # Wrong!

Why it's wrong: The pillow takes n - 1 steps to go from position 1 to n (not n steps), and another n - 1 steps to return.

Solution: Use the correct formula:

cycle_length = (n - 1) * 2

3. Wrong initial direction assumption

Starting with direction = -1 or direction = 0:

Incorrect:

current_position = 1
direction = -1  # Wrong: pillow starts moving forward, not backward

Solution: Always initialize with direction = 1 since the pillow starts moving forward from person 1.

4. Mishandling edge case when time = 0

Some implementations might incorrectly handle the case where time = 0:

Incorrect:

# Processing the move before checking if time is 0
current_position = 1
direction = 1
current_position += direction  # Wrong: moved before checking time
for _ in range(time):
    # ...

Solution: The loop naturally handles time = 0 correctly by not executing any iterations, keeping the pillow at position 1.