Throw Balls: Simulate Ball Throws Between Players and Determine Who Holds the Ball After N Rounds

Question

## Problem

There are `n` players standing in a circle (0-indexed). Player 0 starts with the ball. Each round, the current holder throws the ball to the player `k` positions ahead (wrapping around). After `m` rounds, who has the ball?

```python
def final_holder(n: int, k: int, m: int) -> int:
    pass
```

**Example:**
```
n=5, k=2, m=3
Round 0: Player 0 holds
Round 1: 0 throws to (0+2)%5=2
Round 2: 2 throws to (2+2)%5=4
Round 3: 4 throws to (4+2)%5=1
output -> 1
```

## Approach

Direct formula: `(k * m) % n`. O(1) after simplification.

## Follow-ups
1. Derive the O(1) formula and prove it by induction.
2. What if each player throws by a different step `steps[i]` (the i-th throw goes `steps[i % len(steps)]` positions)? Can you still find a closed form?
3. Extend to multiple balls; balls cannot occupy the same player. How does that change the simulation?
4. Some players are "out" after catching (elimination game like Hot Potato). Who is the last player standing?

Throw Balls: Simulate Ball Throws Between Players and Determine Who Holds the Ball After N Rounds

Question Details

Full Details

Topics

More from Square/Block