algoadvance

Leetcode 2582. Pass the Pillow

Problem Statement

You are given two integers n and time representing the number of people in a circle and the time for passing the pillow respectively. The people are numbered from 1 to n in a clockwise direction.

The pillow starts from person 1. Every second, the pillow is passed to the next person in the clockwise direction. After person n, it goes back to person 1.

Determine who will have the pillow after time seconds.

Example:

Input: n = 4, time = 5
Output: 2
Explanation: 
- At time 0: The pillow is with person 1.
- At time 1: The pillow is with person 2.
- At time 2: The pillow is with person 3.
- At time 3: The pillow is with person 4.
- At time 4: The pillow is again with person 1.
- At time 5: The pillow is with person 2.

Clarifying Questions

  1. Will n always be greater than 1?
  2. Can time be zero or negative?
  3. Are the integers n and time guaranteed to be within a certain range?

Code

class Solution {
public:
    int passThePillow(int n, int time) {
        // The person who will have the pillow after "time" seconds can be calculated using the modulus operation.
        // Since they are numbered from 1 to n, we'll adjust time by n and add 1 to convert 0-based index to 1-based index.
        return (time % n) + 1;
    }
};

Strategy

  1. Identify the cycle in positions: Since the numbering is from 1 to n, after n seconds, the pillow returns back to person 1.
  2. Modulus Operation: The modulus operation (time % n) will give us the cycle position, but since the modulus operation gives a 0-based result, adding 1 will adjust it to 1-based index.
  3. Edge Cases:
    • When n = 1, regardless of time, the result will always be 1.

Time Complexity

The time complexity of this solution is O(1) because the calculation involves basic arithmetic operations. There are no loops or recursive calls involved, making it extremely efficient even for large values of n and time.

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