LeetCode 2582. Pass the Pillow Java Solution
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 bytime / (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:
Store the total number of circles in the variable
arrow
.arrow = time / (n-1)
Store the remaining time in the variable
counter
.counter = time % (n-1)
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).