Find the Winner of the Circular Game
There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the i^th friend brings you to the (i+1)^th friend for 1 <= i < n, and moving clockwise from the n^th friend brings you to the 1^st friend.
The rules of the game are as follows:
- Start at the
1^stfriend. - Count the next
kfriends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once. - The last friend you counted leaves the circle and loses the game.
- If there is still more than one friend in the circle, go back to step
2starting from the friend immediately clockwise of the friend who just lost and repeat. - Else, the last friend in the circle wins the game.
Given the number of friends, n, and an integer k, return the winner of the game.
Follow up: Could you solve this problem in linear time with constant space?
Example 1
Input
n = 5, k = 2Output
3Following the elimination sequence described, friends 2, 4, 1, and 5 leave, so friend 3 is the last remaining winner.
Example 2
Input
n = 6, k = 5Output
1The friends leave in this order: 5, 4, 6, 2, 3, so the winner is friend 1.
Constraints
- 1 <= k <= n <= 500