n people stand in a circle, numbered 0 through n - 1. Starting the count at person 0, count forward k people around the circle (wrapping past the end back to the start) and eliminate whoever the count lands on. Counting for the next elimination resumes with the person immediately after the one just removed.
Keep eliminating one person every k count until a single person is left. Return that survivor's **original** 0-indexed position.
For example, with n = 5 and k = 2: circle is [0, 1, 2, 3, 4]. Counting 2 from person 0 lands on person 1 — eliminate them. Counting 2 from person 2 lands on person 3 — eliminate them. Counting 2 from person 4 wraps to person 0 — eliminate them. Counting 2 from person 2 lands on person 4 — eliminate them. Person 2 is the sole survivor.
Example cases
- five people, count of twoin n = 5, k = 2out 2Eliminations happen in order 1, 3, 0, 4; person 2 survives.
- single personin n = 1, k = 5out 0With only one person in the circle, they survive with no eliminations.
- seven people, count of threein n = 7, k = 3out 3Eliminations happen in order 2, 5, 1, 6, 4, 0; person 3 survives.
Constraints
- 1 <= n <= 10^5
- 1 <= k <= 10^5
5
2