Players numbered 1 through n sit in clockwise order around a circle. Start at player 1 and count k remaining players clockwise, counting the starting player as one and wrapping around as needed. The last player counted is eliminated.
Resume counting from the next remaining player clockwise, again starting at one. Repeat until only one player remains, and return that player's number.
Follow-up: Can you solve this in O(n) time using O(1) extra space?
The diagrams show the remaining players after each elimination, in reading order.
Example 1:
Input: n = 4
k = 2
Output: 1Explanation: The players are eliminated in the order 2, 4, 3. Player 1 remains and wins.
Example 2:
Input: n = 5
k = 1
Output: 5Explanation: With k = 1, each current starting player is eliminated immediately. Players 1, 2, 3, and 4 leave in order, so player 5 wins.
Example 3:
Input: n = 1
k = 1
Output: 1Explanation: Player 1 is already the only player, so no elimination is needed.
Constraints:
1 <= k <= n <= 500