Find the Child Who Has the Ball After K Seconds (LeetCode)

Problem statement:

In a game, n children stand in a circle and pass a ball to each other. The child at position i passes the ball to the child at position (i + 1) % n after 1 second, and the child at position 0 starts with the ball.

You are given the number of children n and the number of seconds k. Return the index of the child who has the ball after k seconds.

Example 1:

Input: n = 5, k = 7 Output: 2

Explanation: The ball will be at child 2 after 7 seconds.

Example 2:

Input: n = 3, k = 4 Output: 1

Explanation: The ball will be at child 1 after 4 seconds.

Constraints:

• 1 <= n <= 10^9
• 1 <= k <= 10^9

Solutions:

Approach 1:

Intuition

The ball passes from one child to the next every second. When the ball reaches the last child (at position n-1), it returns to the first child (at position 0). This forms a repeating cycle of length n.

Approach

Calculate the position of the ball after k seconds by taking the remainder of k divided by n. This will give the current position in the cycle.

Code:

C++

class Solution {
 public:
  int numberOfChild(int n, int k) {
    // the time for the ball to return to 0
    const int roundTime = 2 * (n - 1);
    const int pos = k % roundTime;
    return pos < n ? pos : roundTime - pos;
  }
};

Java

class Solution {
  public int numberOfChild(int n, int k) {
    // the time for the ball to return to 0
    final int roundTime = 2 * (n - 1);
    final int pos = k % roundTime;
    return pos < n ? pos : roundTime - pos;
  }
}

Python

class Solution:
  def numberOfChild(self, n: int, k: int) -> int:
    # the time for the ball to return to 0
    roundTime = 2 * (n - 1)
    pos = k % roundTime
    return pos if pos < n else roundTime - pos

Complexity Analysis:

Approach 1:

Time Complexity: $O(1)$

The time complexity is constant because we only need to perform a few arithmetic operations regardless of the size of $n$ and $k$.

Space Complexity: $O(1)$

The space complexity is also constant because we are only using a fixed amount of extra space for the calculation.