314. Circle of Friends
n friends, numbered 1 to n clockwise, sit around a campfire for a counting game. Counting starts at friend 1, who says 1; the next friend clockwise says 2, and so on. Whoever says k leaves the circle, and the next count starts again from 1 with the friend sitting right after the one who left.
The game continues around the shrinking circle until only one friend remains. Return that friend's number. Removing people one by one with a queue costs O(n * k), which is too slow here, so relate the answer for n friends to the answer for n - 1 friends and avoid simulating the whole game.
Example 1
- Input:
- n = 7, k = 3
- Output:
- 4
- Explanation:
Friends leave in the order 3, 6, 2, 7, 5, 1, and friend 4 is the last one.
Example 2
- Input:
- n = 10, k = 4
- Output:
- 5
- Explanation:
The leaving order is 4, 8, 2, 7, 3, 10, 9, 1, 6 and friend 5 stays until the end.
Constraints
1 ≤ n ≤ 105
1 ≤ k ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)