Players stand in a circle in the order given by names; the potato starts with names[0]. In each round the potato is passed k times to the next player around the circle, and whoever holds it after the k-th pass is eliminated. The next round starts with the player who was standing after the eliminated one.
Return the order in which players are eliminated, with the winner (the last player standing) as the final element.
Examples
Input: names = ["Bill", "David", "Susan", "Jane", "Kent", "Brad"], k = 7
Output: ["David", "Kent", "Jane", "Bill", "Brad", "Susan"]
Explanation: 7 passes around 6 players land on David; then 7 passes among the remaining 5 (starting from Susan) land on Kent, and so on. Susan wins.
Input: names = ["a", "b", "c"], k = 1
Output: ["b", "a", "c"]
Constraints
1 <= len(names) <= 50000 <= k <= 10**9- Target:
O(n * min(k, n))with the modulo trick, or better
Goals
- Model a circle of players with a rotating queue
- Use modulo to avoid passing more times than there are players