Pass the Pillow

Easy

MathWorks

2 views

Topics:

ArraysGreedy Algorithms

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 n^th person they pass it to the n - 1^th person, then to the n - 2^th 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 2^nd 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 3^r^d 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.

Try coding it in LeetCode

Pass the Pillow

Easy

MathWorks

2 views

Topics:

ArraysGreedy Algorithms

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 n^th person they pass it to the n - 1^th person, then to the n - 2^th 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 2^nd 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 3^r^d 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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on `n` and `time`? What is the maximum possible value for each?
Is `n` always greater than or equal to 1, and is `time` always non-negative?
If `n` is equal to 1, what should the output be?
Could you provide a small example to illustrate the expected behavior, especially when the pillow reaches either position 1 or n multiple times?
Do you want me to optimize for time complexity, or is code readability and correctness the priority for this problem?

Brute Force Solution

Approach

The brute force way to solve this problem is like simulating the pillow being passed back and forth, counting each time. We will manually simulate the pillow's journey until the specified number of passes have been made.

Here's how the algorithm would work step-by-step:

Start with the pillow at the first person.
Simulate passing the pillow to the next person in the line.
Keep passing the pillow in the same direction until you reach the end of the line.
When you reach the end of the line, reverse the direction of the pillow.
Keep passing the pillow in the reversed direction until you reach the first person.
Again, reverse the direction of the pillow.
Repeat the process of passing the pillow back and forth, changing directions at each end of the line, until the specified number of passes has been completed.
The person holding the pillow at the end of all the passes is the answer.

Code Implementation

def pass_the_pillow_brute_force(number_of_people, number_of_passes):
    current_position = 1
    direction = 1  # 1 for forward, -1 for backward

    for _ in range(number_of_passes):
        current_position += direction

        # We've reached the end, time to go back
        if current_position > number_of_people:

            current_position = number_of_people - 1
            direction = -1

        # We've reached the start, time to go forward
        elif current_position < 1:

            current_position = 2
            direction = 1

    return current_position

Big(O) Analysis

Time Complexity

O(passes) – The algorithm simulates the passing of the pillow one pass at a time. The number of operations is directly proportional to the number of passes given as input. Therefore, the time complexity is O(passes), where 'passes' represents the number of times the pillow is passed. 'n', the number of people, influences the time taken for each pass, but the outer loop, which determines the number of passes, is dictated solely by the 'passes' input.

Space Complexity

O(1) – The described brute-force solution simulates the pillow passing process. It uses a constant number of variables, such as the current person holding the pillow and the direction of the pass, regardless of the number of people (N) or the number of passes. Therefore, no auxiliary data structures scale with the input size. The space complexity is constant.

Optimal Solution

Approach

The most efficient way to solve this problem involves understanding the pattern of movement back and forth. Instead of simulating each pass of the pillow, we can directly calculate where the pillow will be after a certain number of passes by using some math related to cycles.

Here's how the algorithm would work step-by-step:

First, figure out how long it takes for the pillow to make a complete round trip, going from the first person to the last and then back to the first.
Next, determine how many complete round trips the pillow makes based on the given number of passes.
After figuring out the full round trips, focus on the remaining passes. These remaining passes are what determine the final position.
If the remaining passes are less than or equal to the number of people minus one, the pillow is moving forward. Calculate the position by simply adding the remaining passes to the starting position.
If the remaining passes are more than the number of people minus one, the pillow has reached the end and is moving backward. Adjust the calculation accordingly to find the person holding the pillow as it moves back.
Finally, return the position (person's number) where the pillow ends up after all the passes.

Code Implementation

def pass_the_pillow(number_of_people, number_of_passes):
    round_trip_length = (number_of_people - 1) * 2

    number_of_remaining_passes = number_of_passes % round_trip_length

    # Determine if the pillow is moving forward or backward
    if number_of_remaining_passes <= number_of_people - 1:
        pillow_position = 1 + number_of_remaining_passes

    else:
        # Account for the 'backward' part of the cycle
        pillow_position = number_of_people - (number_of_remaining_passes - (number_of_people - 1))

    return pillow_position

Big(O) Analysis

Time Complexity

O(1) – The solution involves a fixed number of arithmetic operations regardless of the number of people or passes. We calculate the round trip length, determine the number of full round trips, and then calculate the final position based on the remaining passes. All these steps involve constant time calculations using modulo and conditional statements. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The provided solution calculates the final position directly using mathematical operations based on the input values (number of people and number of passes). It doesn't involve creating any auxiliary data structures like arrays, lists, or hash maps. Only a few variables are used to store intermediate results of calculations. Therefore, the space complexity remains constant irrespective of the input size N (number of people) and is O(1).

Edge Cases

Case	How to Handle
n = 1 (only one person)	Always return 1, as the pillow stays with the first person
time = 0 (no passing occurs)	Return 1, as the pillow starts with the first person
time is a large number causing integer overflow in intermediate calculations	Use long data type for 'time' to avoid potential overflow during calculation
time is exactly divisible by (n-1)*2	The pillow returns to the starting position 1, so handle the case when the cycle completes an exact number of times
time is close to the maximum integer value	Ensure intermediate calculations don't overflow even with 'long' data type
n is a small number, such as 2	Handle the case of two people, where the direction changes every time
n is equal to Integer.MAX_VALUE (extreme boundary value for number of positions)	The solution may not be efficient due to calculations involving large numbers, consider using modular arithmetic appropriately
n is a negative number or zero.	Return an error or throw an exception as 'n' represents a count of people and cannot be non-positive.