Find the Winner of the Circular Game
MedPrompt
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 ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.
The rules of the game are as follows:
- Start at the
1stfriend. - 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.
Example 1:
Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.Example 2:
Input: n = 6, k = 5
Output: 1
Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.
Constraints:
1 <= k <= n <= 500
Follow up:
Could you solve this problem in linear time with constant space?
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward approach that directly simulates the game as described. We use a dynamic list, like an ArrayList, to keep track of the friends currently in the circle. In each round, we find and remove the friend who is counted out.
Algorithm
- Initialize a list (e.g.,
ArrayList) with numbers from 1 ton. - Keep track of the starting position for counting in each round, let's call it
currentIndex, initialized to 0. - Loop as long as the size of the list is greater than 1.
- In each iteration, calculate the index of the friend to be removed. The formula is
(currentIndex + k - 1) % list.size(). - Remove the friend at the calculated index.
- The
currentIndexfor the next round will be the same as the removal index, as the list elements shift to the left after removal. - After the loop terminates, the list will contain a single element, which is the winner.
Walkthrough
The core idea is to use a list to represent the circle of friends. We start with a list containing numbers from 1 to n. We also maintain a pointer, currentIndex, to know where to start counting in each round. The game proceeds in rounds, with one friend being eliminated in each round. The loop continues as long as there is more than one friend. To find which friend to eliminate, we advance k-1 steps from currentIndex, wrapping around the list using the modulo operator. After removing the friend, the list shrinks, and the element that was to the right of the removed one now occupies its position. This becomes our new currentIndex for the next round. Finally, when only one friend is left, they are the winner.
import java.util.ArrayList;import java.util.List; class Solution { public int findTheWinner(int n, int k) { List<Integer> friends = new ArrayList<>(); for (int i = 1; i <= n; i++) { friends.add(i); } int currentIndex = 0; while (friends.size() > 1) { int removalIndex = (currentIndex + k - 1) % friends.size(); friends.remove(removalIndex); // The next starting position is the same as the removal index // because the list shifts left. currentIndex = removalIndex; } return friends.get(0); }}Complexity
Time
O(n^2) - The simulation runs for `n-1` rounds. In each round, removing an element from an `ArrayList` can take up to O(n) time because all subsequent elements must be shifted.
Space
O(n) - We need a list to store the `n` friends.
Trade-offs
Pros
Simple to understand and implement.
Directly models the game's rules.
Cons
Inefficient for large
ndue to the costly O(n) removal operation in a list.
This approach also simulates the game but uses a more suitable data structure, a queue, to optimize the process. A queue (implemented as a LinkedList) allows for efficient removal from the front (O(1)). We simulate the 'counting' by rotating the elements of the queue.
Algorithm
- Initialize a queue (e.g.,
LinkedList) and enqueue all friend numbers from 1 ton. - Loop while the queue contains more than one friend.
- To find the
k-th friend, performk-1rotations. In each rotation, dequeue an element from the front and enqueue it to the back. - After
k-1rotations, the friend at the front of the queue is the one to be eliminated. Simply dequeue them. - Repeat this process until only one friend is left in the queue.
- The last remaining element in the queue is the winner.
Walkthrough
To avoid the expensive removal operation of the list-based approach, we can use a queue. A queue provides constant time add (enqueue) and poll (dequeue) operations. We first populate the queue with all n friends. The game proceeds in rounds until one friend is left. In each round, instead of moving a pointer, we rotate the queue. To get to the k-th person, we dequeue k-1 people from the front and immediately enqueue them to the back. After these rotations, the person to be eliminated is conveniently at the front of the queue. We can then remove them with a single poll() operation. This process is repeated until the queue has only one element, which is the winner.
import java.util.LinkedList;import java.util.Queue; class Solution { public int findTheWinner(int n, int k) { Queue<Integer> queue = new LinkedList<>(); for (int i = 1; i <= n; i++) { queue.add(i); } while (queue.size() > 1) { // Move k-1 friends from the front to the back of the queue. for (int i = 0; i < k - 1; i++) { queue.add(queue.poll()); } // The k-th friend is now at the front, so we remove them. queue.poll(); } return queue.peek(); }}Complexity
Time
O(n * k) - The main loop runs `n-1` times. Inside, we perform `k-1` queue rotations, each taking O(1) time. Thus, the total time is proportional to `n * k`.
Space
O(n) - A queue is used to store the `n` friends.
Trade-offs
Pros
More efficient than the list approach if
kis small.Conceptually clean way to handle a circular arrangement.
Cons
Performance degrades as
kincreases, becoming O(n^2) in the worst case.Still requires O(n) auxiliary space.
This problem is a classic variant of the Josephus Problem, which can be solved efficiently using a mathematical recurrence relation. Instead of simulating the entire game, we can directly compute the winner's position. This approach offers the best performance by avoiding simulation altogether and meets the follow-up challenge of linear time and constant space.
Algorithm
- This problem is a variant of the Josephus Problem, which has a mathematical solution based on a recurrence relation.
- Let
f(n, k)be the 0-indexed position of the winner withnpeople and stepk. - The base case is
f(1, k) = 0. - The recurrence relation is
f(n, k) = (f(n-1, k) + k) % n. - We can solve this iteratively by starting with the base case for
n=1and building up the solution ton. - Start with
winner_pos = 0(forn=1). - Loop from
i = 2ton, updating the position withwinner_pos = (winner_pos + k) % i. - The final result is the 0-indexed
winner_posconverted to a 1-indexed number by adding 1.
Walkthrough
The most efficient solution leverages the mathematical properties of the problem. Let's define f(n, k) as the position of the winner in a 0-indexed circle of n people. When we eliminate the first person (at index (k-1)%n), we are left with a smaller problem of n-1 people. The key insight is to relate the solution of the n-1 person problem back to the n person problem. The winner's position in the n-1 person circle, f(n-1, k), can be mapped back to the original circle, leading to the recurrence relation: f(n, k) = (f(n-1, k) + k) % n. We can solve this iteratively for optimal performance. We start with the solution for one person, f(1, k) = 0, and iteratively apply the formula to find the solution for 2, 3, ..., up to n people. This avoids recursion and uses constant extra space. The final 0-indexed result is then converted to the 1-indexed friend number required by the problem.
class Solution { public int findTheWinner(int n, int k) { // The position of the winner in a 0-indexed circle of i people // is given by f(i) = (f(i-1) + k) % i. int winnerPosition = 0; // Base case: f(1, k) = 0 // Iteratively compute the winner's position for 2, 3, ..., n people. for (int i = 2; i <= n; i++) { winnerPosition = (winnerPosition + k) % i; } // Convert the 0-indexed position to a 1-indexed friend number. return winnerPosition + 1; }}Complexity
Time
O(n) - The solution uses a single loop that iterates from 2 to `n`, performing constant time operations inside.
Space
O(1) - The iterative solution uses only a few variables, requiring constant extra space.
Trade-offs
Pros
Optimal solution with linear time and constant space complexity.
Extremely fast for large
n.
Cons
The logic is abstract and less intuitive than direct simulation.
Requires knowledge of the underlying recurrence relation.
Solutions
Solution
class Solution {public int findTheWinner(int n, int k) { if (n == 1) { return 1; } int ans = (findTheWinner(n - 1, k) + k) % n; return ans == 0 ? n : ans; }}/** * @param {number} n * @param {number} k * @return {number} */ var findTheWinner = function (n, k) { if (n === 1) { return 1; } const ans = (k + findTheWinner(n - 1, k)) % n; return ans ? ans : n; };class Solution: def findTheWinner(self, n: int, k: int) -> int: if n == 1: return 1 ans = (k + self . findTheWinner(n - 1, k)) % n return n if ans == 0 else ansclass Solution {public: int findTheWinner(int n, int k) { if (n == 1) return 1; int ans = (findTheWinner(n - 1, k) + k) % n; return ans == 0 ? n : ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.