algoadvance

Leetcode 2582. Pass the Pillow

Problem Statement

Alice and Bob play a game with a pillow. Initially, Alice has the pillow. They pass the pillow to the next person every second.

Given two integers n (the number of people in the circle) and time, return the index of the person who has the pillow after time seconds.

The people in the circle are indexed from 1 to n.

Example 1:

Input: n = 4, time = 5
Output: 2
Explanation:
Alice starts with the pillow at time 0.
After 1 second, Alice passes the pillow to Bob.
After 2 seconds, Bob passes the pillow to the 3rd person.
After 3 seconds, the 3rd person passes the pillow to the 4th person.
After 4 seconds, the 4th person passes the pillow to Alice.
After 5 seconds, Alice passes the pillow to Bob.

Example 2:

Input: n = 3, time = 2
Output: 3
Explanation:
Alice starts with the pillow at time 0.
After 1 second, Alice passes the pillow to Bob.
After 2 seconds, Bob passes the pillow to the 3rd person.

Clarifying Questions

  1. Does the sequence of passing always involve starting from Alice and then moving one step clockwise?
    • Yes, the sequence starts from Alice (index 1) and moves to the next person in a circular manner.
  2. Can n be as small as 1?
    • For simplicity, let’s assume n >= 2.
  3. Are there any constraints on the values of n and time?
    • The constraint values are within reasonable limits for a simple modular arithmetic solution.

Strategy

  1. Circular Passing Mechanism:
    • If we consider the number of passes (or seconds) time within an n-person circle, the problem translates to a modulo operation. Essentially, after every n seconds, the sequence restarts.
  2. Calculation:
    • We can use the modulo operation to determine the position directly. ((time - 1) % n) + 1.

Code

Here’s the implementation:

public class PillowGame {
    public int passThePillow(int n, int time) {
        return ((time - 1) % n) + 1;
    }

    public static void main(String[] args) {
        PillowGame pg = new PillowGame();
        System.out.println(pg.passThePillow(4, 5));  // Output: 2
        System.out.println(pg.passThePillow(3, 2));  // Output: 3
    }
}

Time Complexity

The time complexity of this solution is constant, O(1), because:

The space complexity is also O(1) since we are not using any additional space that scales with input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI