algoadvance

You are given an integer n representing the number of people in a circle and an integer time representing the total time (in minutes) that the pillow has been passed around.

The pillow passing starts with the first person and moves to the next person every minute. The direction of passing needs to alternate each time, one minute to the right, one minute to the left, and so on.

Write a function pass_the_pillow(n: int, time: int) -> int that returns the position of the person who receives the pillow after the given amount of time.

Clarifying Questions

  1. Initial Position: Does the passing start from the first person?
    • Yes, the passing starts from the first person, i.e., position 1.
  2. Direction Changes: Should the direction change at every unit of time?
    • Yes, the direction changes alternately every unit of time: right, left, right, left, and so on.
  3. Time and People Relation: Is it guaranteed that time and the number of people will be valid inputs?
    • Yes, assume that time is non-negative and n is greater than 0.

Code

def pass_the_pillow(n: int, time: int) -> int:
    # Initial position of the pillow, start from person 1
    position = 1
    
    # determine full cycles and remaining moves
    full_cycles, remainder = divmod(time, n-1)
    
    # If full_cycles is even, final direction will be same as initial, right
    if full_cycles % 2 == 0:
        # Moving to the right by remainder
        position = (position - 1 + remainder) % n + 1
    else:
        # Moving to the left by remainder
        position = (position - 1 - remainder) % n + 1
    
    return position

# Test case
print(pass_the_pillow(4, 5))  # Output should be 1

Strategy

  1. Initialize: Start with position 1.
  2. Compute Full Cycles: Calculate how many full cycles (n-1 passes make a full cycle) the pillow has completed.
  3. Determine Remainder: Calculate the remainder which tells how many passes are left after full cycles.
  4. Final Position Calculation:
    • If the total number of full cycles is even, the final direction is right. Move right by the remainder.
    • If the total number of full cycles is odd, the final direction is left. Move left by the remainder.

Time Complexity

Try our interview co-pilot at AlgoAdvance.com