Problem

You are given two positive integers n and k. There are n children numbered from 0 to n - 1 standing in a queue in order from left to right.

Initially, child 0 holds a ball and the direction of passing the ball is towards the right direction. After each second, the child holding the ball passes it to the child next to them. Once the ball reaches either end of the line, i.e. child 0 or child n - 1, the direction of passing is reversed.

Return the number of the child who receives the ball after k seconds.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Input: n = 3, k = 5

Output: 1

Explanation:

Time elapsed | Children  
---|---  
`0` | `[_0_ , 1, 2]`  
`1` | `[0, _1_ , 2]`  
`2` | `[0, 1, _2_]`  
`3` | `[0, _1_ , 2]`  
`4` | `[_0_ , 1, 2]`  
`5` | `[0, _1_ , 2]`

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


Input: n = 5, k = 6

Output: 2

Explanation:

Time elapsed | Children  
---|---  
`0` | `[_0_ , 1, 2, 3, 4]`  
`1` | `[0, _1_ , 2, 3, 4]`  
`2` | `[0, 1, _2_ , 3, 4]`  
`3` | `[0, 1, 2, _3_ , 4]`  
`4` | `[0, 1, 2, 3, _4_]`  
`5` | `[0, 1, 2, _3_ , 4]`  
`6` | `[0, 1, _2_ , 3, 4]`

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


Input: n = 4, k = 2

Output: 2

Explanation:

Time elapsed | Children  
---|---  
`0` | `[_0_ , 1, 2, 3]`  
`1` | `[0, _1_ , 2, 3]`  
`2` | `[0, 1, _2_ , 3]`

Constraints

  • 2 <= n <= 50
  • 1 <= k <= 50

Note: This question is the same as 2582: Pass the Pillow.

Solution

Method 1 – Simulation with Modulo Arithmetic

Intuition

The ball moves back and forth between the ends. The movement forms a cycle of length 2 * (n - 1). We can use modulo arithmetic to find the position after k seconds efficiently.

Approach

  1. Compute the cycle length as 2 * (n - 1).
  2. The effective time is k % cycle.
  3. If the effective time is less than n, the ball is moving right, so the answer is effective time.
  4. Otherwise, the ball is moving left, so the answer is cycle - effective time.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int passThePillow(int n, int k) {
        int cycle = 2 * (n - 1);
        int t = k % cycle;
        if (t < n) return t;
        return cycle - t;
    }
};
1
2
3
4
5
6
7
8

func passThePillow(n int, k int) int {
    cycle := 2 * (n - 1)
    t := k % cycle
    if t < n {
        return t
    }
    return cycle - t
}
1
2
3
4
5
6
7
8

class Solution {
    public int passThePillow(int n, int k) {
        int cycle = 2 * (n - 1);
        int t = k % cycle;
        if (t < n) return t;
        return cycle - t;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun passThePillow(n: Int, k: Int): Int {
        val cycle = 2 * (n - 1)
        val t = k % cycle
        return if (t < n) t else cycle - t
    }
}
1
2
3
4
5
6
7

class Solution:
    def passThePillow(self, n: int, k: int) -> int:
        cycle = 2 * (n - 1)
        t = k % cycle
        if t < n:
            return t
        return cycle - t
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn pass_the_pillow(n: i32, k: i32) -> i32 {
        let cycle = 2 * (n - 1);
        let t = k % cycle;
        if t < n {
            t
        } else {
            cycle - t
        }
    }
}
1
2
3
4
5
6
7

class Solution {
    passThePillow(n: number, k: number): number {
        const cycle = 2 * (n - 1);
        const t = k % cycle;
        return t < n ? t : cycle - t;
    }
}

Complexity

  • ⏰ Time complexity: O(1), as only arithmetic operations are used.
  • 🧺 Space complexity: O(1), as only a few variables are used.