Find the Winner of the Circular Game
Problem
n friends 1..n stand in a circle. Starting from friend 1, count k around and that friend leaves; continue with the next remaining. Return the winner.
n = 5, k = 23from collections import deque
def find_the_winner(n, k):
q = deque(range(1, n + 1))
while len(q) > 1:
for _ in range(k - 1):
q.append(q.popleft())
q.popleft()
return q[0]function findTheWinner(n, k) {
const q = [];
for (let i = 1; i <= n; i++) q.push(i);
let head = 0;
while (q.length - head > 1) {
for (let i = 0; i < k - 1; i++) { q.push(q[head++]); }
head++;
}
return q[head];
}class Solution {
public int findTheWinner(int n, int k) {
Deque<Integer> q = new ArrayDeque<>();
for (int i = 1; i <= n; i++) q.add(i);
while (q.size() > 1) {
for (int i = 0; i < k - 1; i++) q.addLast(q.pollFirst());
q.pollFirst();
}
return q.peek();
}
}int findTheWinner(int n, int k) {
deque<int> q;
for (int i = 1; i <= n; i++) q.push_back(i);
while ((int)q.size() > 1) {
for (int i = 0; i < k - 1; i++) { q.push_back(q.front()); q.pop_front(); }
q.pop_front();
}
return q.front();
}Explanation
This is the classic Josephus elimination, and the most direct way to solve it is to simulate the circle with a queue. The front of the queue is "the next person being counted," and rotating people to the back mimics walking around the ring.
We fill the queue with friends 1..n. To eliminate the k-th person, we move the first k-1 people from the front to the back (counting past them), then popleft the person now at the front — that is the one who is out.
Sending survivors to the back keeps the relative order intact, so counting always continues from the spot right after whoever just left. We repeat until a single friend remains, and that friend is the winner.
Example: n = 5, k = 2. Counting by twos eliminates 2, then 4, then 1, then 5, in that order, leaving 3 as the winner.
Each of the n-1 removals does up to k-1 rotations, so the simulation is O(n·k) time with O(n) space for the queue.