We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Pass the Pillow

Number: 2645

Difficulty: Easy

Paid? No

Companies: MathWorks, Google

Problem Description

There are n people standing in a line numbered from 1 to n. Initially, the first person holds a pillow. Every second, the pillow is passed to the adjacent person in the current direction. When the pillow reaches one end of the line, the passing direction reverses. Given two positive integers n and time, determine the index of the person holding the pillow after time seconds.

Key Insights

  • The passing of the pillow follows a back-and-forth pattern.
  • The cycle length is 2 * (n - 1) seconds, which represents a full pass from the first person to the last and back.
  • Use modulo arithmetic with the cycle length to determine the effective position after the given time.

Space and Time Complexity

Time Complexity: O(1) - Calculation involves simple arithmetic operations. Space Complexity: O(1) - Only a fixed number of variables are used.

Solution

We first compute the effective time within a full cycle using remainder = time % (2 * (n - 1)). If the remainder is less than (n - 1), it means the pillow is still moving from the start towards the end, and the result is remainder + 1. If it is greater or equal to (n - 1), the pillow is moving back toward the start, so the result is n - (remainder - (n - 1)). This approach eliminates the need for simulation while correctly handling the back-and-forth movement.

Code Solutions

# Python solution with line-by-line comments

def passThePillow(n, time):
    # Calculate the cycle length: going from 1 to n and back to 1
    cycle_length = 2 * (n - 1)
    
    # Find the effective time within one cycle
    remainder = time % cycle_length

    # If remainder is less than n-1, pillow is moving forward (1-indexed)
    if remainder < n:
        return remainder + 1
    # Otherwise, pillow is moving backward
    else:
        return n - (remainder - (n - 1))

# Example usage
print(passThePillow(4, 5))  # Expected output: 2
← Back to All Questions