LeetCode 2582. Pass the Pillow Java Solution

·

2 min read

Problem Description

  • Problem: https://leetcode.com/problems/pass-the-pillow/description/

  • Description: People are standing in a circle numbered from 1 to n. Person 1 holds a pillow and every hour they pass the pillow to the person to their right. If the pillow reaches the last person, it is passed back to person 1. Return the number of the person who has the pillow after time hours.

Approach

  • Idea:

    • To make the problem easier to understand, we first calculate how many complete circles the pillow passes through.

    • Each circle takes n-1 hours to complete, so we can calculate the total number of circles by time / (n-1).

      • For example, if n is 4, it takes 3 moves to reach person 4. 1→2→3→4
    • After that, we calculate the remaining time using time % (n-1) to determine which person gets the pillow in the last circle.

    • Depending on whether the number of complete circles is even or odd, the direction of the last pass changes. For even circles, the pillow moves forward, while for odd circles, it moves backward.

  • Algorithm:

    1. Store the total number of circles in the variable arrow. arrow = time / (n-1)

    2. Store the remaining time in the variable counter. counter = time % (n-1)

    3. Calculate the result based on whether arrow is even or odd.

      • If arrow is even, the pillow is passed forward: 1 + counter

      • If arrow is odd, the pillow is passed backward: n - counter

Code

class Solution {
    public int passThePillow(int n, int time) {
        int arrow = time / (n-1);
        int counter = time % (n-1);
        int result;

        if (arrow % 2 != 0) {
            result = n - counter;
        } else {
            result = 1 + counter;
        }

        return result;
    }
}

Conclusion

  • Time Complexity:

    • All operations are performed in constant time, so the time complexity is O(1).
  • Space Complexity:

    • Since we use only a few additional variables, the space complexity is O(1).

Did you find this article valuable?

Support Han by becoming a sponsor. Any amount is appreciated!