Problem of The Day: Pass the Pillow

Problem Statement

Intuition

The problem can be visualized as people standing in a line, passing a pillow back and forth. We need to determine which person has the pillow after a given amount of time time.

Approach

1. Initialization:

   • Start at the first person, i = 1.
   • Use a boolean flag isLeftToRight to track the direction of the pillow passing (left-to-right or right-to-left).

2. Simulate Passing the Pillow:

   • Continue the process until the given time runs out.
   • If the current direction is left-to-right (isLeftToRight is True):
     • Increment the position i.
     • If the pillow reaches the last person (i == n), change direction.
   • If the current direction is right-to-left (isLeftToRight is False):
     • Decrement the position i.
     • If the pillow reaches the first person (i == 1), change direction.

3. Return the Final Position:

   • After the loop finishes, the current value of i will be the person who has the pillow.

Complexity

• Time Complexity:
  • The loop runs time times, making the time complexity (O(\text{time})).
• Space Complexity:
  • Only a few variables are used regardless of input size, making the space complexity (O(1)).

Code

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        i = 1
        isLeftToRight = True
        while time > 0:
            if isLeftToRight:
                i += 1
                if i == n:
                    isLeftToRight = not isLeftToRight
            else:
                i -= 1
                if i == 1:
                    isLeftToRight = not isLeftToRight
            time -= 1

        return i

Editorial

Approach 1: Simulation

class Solution:
    def passThePillow(self, n: int, time: int) -> int:
        current_pillow_position = 1
        current_time = 0
        direction = 1
        while current_time < time:
            if 0 < current_pillow_position + direction <= n:
                current_pillow_position += direction
                current_time += 1
            else:
                # Reverse the direction if the next position is out of bounds
                direction *= -1
        return current_pillow_position

Math

class Solution:
    def passThePillow(self, n, time):
        # Calculate the number of complete rounds of pillow passing
        full_rounds = time // (n - 1)

        # Calculate the remaining time after complete rounds
        extra_time = time % (n - 1)

        # Determine the position of the person holding the pillow
        # If full_rounds is even, the pillow is moving forward.
        # If full_rounds is odd, the pillow is moving backward.
        if full_rounds % 2 == 0:
            return extra_time + 1  # Position when moving forward
        else:
            return n - extra_time  # Position when moving backward