algoadvance

You are playing a game with n children standing in a circle, numbered from 0 to n-1. Initially, the child at position 0 has a ball. The game proceeds for k seconds. Every second, the child who has the ball passes it to the next child in the circle, i.e., the ball moves from position i to position (i+1) % n.

Write a function that returns the position of the child with the ball after k seconds.

Function Signature

def child_with_ball(n: int, k: int) -> int:
    pass

Example

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

Constraints

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

Clarifying Questions

1. Q: Do we always start with the ball at position 0? A: Yes, the ball always starts at position 0.

2. Q: Are the children numbered consecutively starting from 0? A: Yes, they are numbered consecutively from 0 to n-1.

3. Q: Is the ball always passed in increasing order of children numbers? A: Yes, the ball is passed to the next child in the sequence (i+1) % n.

Strategy

Given that we need to determine the position of the child after k seconds with n children, we can use the properties of the modulo operation to simplify our task:

1. Start with the initial position of the ball at 0.
2. Each second, the ball moves from i to (i+1) % n.
3. After k seconds, the position of the ball can be determined by:
   • The initial position 0 plus k positions forward.
   • Taking modulo n, i.e., (0 + k) % n, which simplifies to k % n.

Thus, the position of the child who has the ball after k seconds is effectively k % n.

Time Complexity

• The computation involves a simple modulo operation, making the time complexity O(1).

Code

def child_with_ball(n: int, k: int) -> int:
    return k % n

Let’s break down an example:

• For n = 5 and k = 2, the ball moves two positions from 0:
  • Position after 1 second: 1
  • Position after 2 seconds: 2 So, child_with_ball(5, 2) = 2.

We can see that modulo operation directly gives us this value.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?