2582. Pass the Pillow

EasyMathSimulation
Leetcode Link

Problem Description

In this problem, we have n people standing in a line numbered from 1 to n. The unique feature here is an ongoing game where a pillow is being passed among them. The game starts with the first person and the pillow is passed one person at a time every second in a linear fashion. When the pillow reaches the last person, it changes direction and starts to go back towards the first person. This back and forth continues perpetually with no end. The challenge is to calculate the position of the person holding the pillow after a given number of seconds, referred to as time.

It's important to understand the flow of the game here: It is akin to a ping-pong ball going back and forth on a linear table. Each traverse from the start to the end and back to the start constitutes what can be thought of as a "round" in the game.

The task is to determine who exactly is holding the pillow after a specified time has passed, with just two elements in hand - the number of people n and the passage of time.

Intuition

To tackle this problem, we immediately recognize that the core of it is repetitive patterns over time. With every n - 1 seconds, the pillow returns to the start or the last person, depending on the direction it's currently moving in. This realization helps us understand that time can be broken down into chunks of n - 1 seconds, after which the system essentially resets.

Understanding this cyclical nature, we can calculate the number of complete cycles (k) and the remainder, which is the position of the extra passes (mod). This is done through simple integer division and modulo operations. From there, the direction of pillow travel after complete cycles is key to finding the final position. If k is even, the pillow is moving towards the end, and if k is odd, it's moving towards the start.

Now we look at the remainder mod. If the pillow is moving towards the end (k is even), the person holding the pillow will be mod + 1 (because we index from 1, not 0). If it's moving towards the start (k is odd), the person holding the pillow will be n - mod. The solution hinges on these insights, and the code is simply an implementation of this logic.

By encapsulating the process in a mathematical formula, we achieve a solution that operates in constant time O(1), which is tremendously more efficient than simulating the entire process in O(time) complexity.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is a min heap?

Solution Approach

The implementation of the solution follows a mathematical approach rather than a simulation. This choice is rooted in a desire for efficiency as simulating the pillow passing process could take linear time, which is not optimal when time is a large number.

Algorithm

The algorithm used is quite straightforward once the pattern in the pillow passing game is recognized:

  1. Calculate the number of complete passes (each pass spanning n - 1 seconds) and the remaining seconds after these complete passes using integer division and modulo operations. This is done through the divmod function in Python which returns a tuple containing the quotient and the remainder.

  2. Determine the direction of the pillow passing for the current pass (whether it's going towards the end or towards the start of the line). This is derived from whether the number of complete rounds k is even or odd.

  3. Based on the direction and the remainder, calculate the position of the person who will be holding the pillow after the specified time.

Data Structures

In this solution, there are no special data structures used. The algorithm operates with simple integers and therefore requires no more than a few variables to execute.

Patterns

The following pattern is used:

  • Modulo arithmetic: Helps cycle through the people in a linear fashion and to represent the cyclical nature of the pillow passing.
  • Even-odd parity: Determines the direction of the pillow passing, using the parity of the number of complete cycles.

Code Explanation

The solution code is a direct application of the identified pattern:

1class Solution:
2    def passThePillow(self, n: int, time: int) -> int:
3        # Calculate the number of complete rounds 'k' and the remainder 'mod'
4        k, mod = divmod(time, n - 1)
5      
6        # If 'k' is even, the direction is towards the end, and the position is 'mod + 1'
7        # If 'k' is odd, the direction is towards the start, and the position is 'n - mod'
8        return n - mod if k & 1 else mod + 1

In the code, k & 1 is used as a quick check for odd parity, as checking the least significant bit is a common way to check if an integer is odd (k & 1 would be 1 for odd numbers).

In conclusion, the solution leverages mathematical properties of cycles to deduce the position of the person with the pillow at any given time, making it an elegant and efficient approach to the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the maximum element can be found in:

Example Walkthrough

Let’s consider n = 5 people in the line and time = 13 seconds to illustrate the solution approach. Here’s how we apply the algorithm step by step:

  1. Calculate the complete rounds 'k' and the remainder 'mod':

    • Since there are 5 people, each full round takes 5 - 1 = 4 seconds.
    • After 13 seconds, k = 13 // 4 = 3 complete rounds have occurred.
    • The remainder mod = 13 % 4 = 1 second is the extra time after the last complete round.

  2. Determine the direction of the pillow passing:

    • The number of complete rounds k = 3 is odd, indicating that after 3 complete rounds, the pillow is moving towards the start.

  3. Based on the direction and the remainder, calculate the position:

    • We determined that the pillow is moving towards the start (k is odd).
    • With a remainder of mod = 1 and n = 5, the final position is n - mod (5 - 1) = 4.

Using this approach, we can conclude that after 13 seconds, the 4th person in the line will be holding the pillow.

Solution Implementation

1class Solution:
2    def passThePillow(self, num_people: int, time: int) -> int:
3        # Find how many full cycles are there and what's the remainder time after the cycles
4        full_cycles, remainder_time = divmod(time, num_people - 1)
5      
6        # If the number of full cycles is odd, the game is moving in reverse
7        if full_cycles % 2 == 1:
8            # Compute the current holder's position during reverse passing
9            # If remainder_time is 0, it means the pillow is at the starting position
10            # So the last person will have the pillow, otherwise calculate from the end
11            final_position = num_people - remainder_time
12        else:
13            # If the number of full cycles is even, the game is moving normally
14            # The current holder's position will be remainder_time + 1,
15            # since positions are 1-indexed
16            final_position = remainder_time + 1
17      
18        return final_position
19
20# Example:
21# num_people = 4, time = 7
22# full_cycles = 1 (one full reverse cycle), remainder_time = 3
23# final_position = 4 - 3 = 1 (1-indexed)
24
1class Solution {
2
3    /**
4     * Determines the final position of the pillow after a specified time.
5     *
6     * @param totalParticipants the number of participants in the game.
7     * @param totalTime the total time for which the pillow is passed.
8     * @return the final position of the pillow after the specified time.
9     */
10    public int passThePillow(int totalParticipants, int totalTime) {
11        // Compute the number of complete rounds that have been made
12        int completeRounds = totalTime / (totalParticipants - 1);
13      
14        // Compute the remaining time after the complete rounds
15        int remainingTime = totalTime % (totalParticipants - 1);
16
17        // If the number of complete rounds is odd, the direction of passing is reversed
18        // Since the passing starts with participant 1, the final position will be counted backwards
19        // from the total number of participants
20        if ((completeRounds & 1) == 1) {
21            return totalParticipants - remainingTime;
22        } else {
23            // If the number of complete rounds is even, the final position will be counted forward
24            // The '+1' is required to adjust the position to a 1-indexed based
25            return remainingTime + 1;
26        }
27    }
28}
29
1class Solution {
2public:
3    // Function to find the final position of the pillow after 'time' passes
4    int passThePillow(int numPeople, int time) {
5        // Determine how many complete rounds the pillow makes
6        int completeRounds = time / (numPeople - 1);
7      
8        // Calculate the remaining time after the complete rounds
9        int remainingTime = time % (numPeople - 1);
10      
11        // If the number of complete rounds is odd, the direction of passing is reversed
12        if (completeRounds % 2 == 1) {
13            // The pillow is moving in the reverse direction with (n - remainingTime) people to pass
14            // If remainingTime is 0, pillow stays at the starting person, and position is numPeople
15            return remainingTime == 0 ? numPeople : numPeople - remainingTime;
16        } else {
17            // The pillow is moving in the forward direction with remainingTime people to pass
18            // If remainingTime is 0, pillow stays at the starting person, and position is 1
19            return remainingTime == 0 ? 1 : remainingTime + 1;
20        }
21    }
22};
23
1function passThePillow(numberOfPlayers: number, musicTime: number): number {
2    // Determine the number of full cycles by dividing the music time by the number of turns
3    const fullCycles = Math.floor(musicTime / (numberOfPlayers - 1));
4  
5    // Calculate the remaining time after the full cycles
6    const remainingTime = musicTime % (numberOfPlayers - 1);
7
8    // If the number of full cycles is odd, the pillow moves in reverse order
9    // Calculate the player position based on the remaining time
10    if (fullCycles % 2 === 1) {
11        return numberOfPlayers - remainingTime;
12    } else {
13        // If the number of full cycles is even, the pillow moves in forward order
14        // Calculate the player position based on the remaining time
15        return remainingTime + 1;
16    }
17}
18
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

The given code calculates which person will have the pillow after a certain amount of time in a game where the pillow is passed around in a circle. The function passThePillow computes the position using basic arithmetic operations.

  • Time Complexity: The divmod function that is used to calculate both the quotient k and remainder mod of time divided by n - 1 is an inbuilt Python function operating in constant time. After divmod, there are only a handful of basic operations (addition, subtraction, and bitwise operation). These operations also take constant time. Therefore, the overall time complexity of the function is O(1).

  • Space Complexity: The function only uses a fixed amount of extra space to store the variables k and mod, and no additional space that scales with the input size is used. Therefore, the space complexity of the function is O(1).

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫