DSA problem
Find the Winner of the Circular Game
There are n friends playing a game. The friends are sitting in a circle and numbered from 1 to n in clockwise order. The rules are: starting at friend 1, count the next k friends in the clockwise direction including the friend you started at; the last counted friend leaves the circle and loses the game; the next friend (clockwise from the one who just left) becomes the new starting point, and the game continues with one fewer friend in the circle. The game ends when there is exactly one friend left, who is declared the winner. Return that winner's number.
This is the famous Josephus problem. A direct queue simulation is intuitive: place 1..n into a queue, and repeat until only one element remains — rotate k - 1 elements from front to back, then pop the front. Each round removes one player after k rotations, so the total work is O(n * k) time and O(n) space. For small to moderate n this is perfectly fast and very readable.
There is also a beautiful closed-form recurrence. If f(m, k) denotes the 0-indexed position of the winner among m people, then f(1, k) = 0 and f(m, k) = (f(m - 1, k) + k) % m. The recurrence captures the fact that after the first elimination of position (k - 1) % m everyone else's positions shift by k modulo the new size. Converting back to 1-indexing gives the answer f(n, k) + 1. The recursive version uses O(n) stack space, but an iterative loop computes the same value in O(n) time and O(1) extra space.
We present the queue simulation as the canonical approach because it teaches the problem structurally, with a tiny note inside the solution that the DP recurrence delivers an even tighter O(n) variant.
Examples
n = 5, k = 23n = 6, k = 51n = 1, k = 71Constraints
- 1 <= k <= n <= 500
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.