Skip to main content
Talentd

Find the Winner of the Circular Game - Solution & Explanation

MediumArrayMathRecursionQueue15 min readAsked at: Amazon, Microsoft, Goldman Sachs +9
Practice this problem

Problem Statement

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:

  1. Start at the 1st friend.
  2. Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
  3. The last friend you counted leaves the circle and loses the game.
  4. If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
  5. 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?

Approach Overview

Problem Overview: You have n friends standing in a circle. Starting from the first friend, every k-th friend is eliminated until only one person remains. The task is to return the label of the final survivor. This is a classic variation of the Josephus problem often solved with simulation or a direct mathematical recurrence.

Approach 1: Simulating the Process with a List (O(n*k) time, O(n) space)

This approach directly models the game. Store players 1..n in a list or queue and repeatedly remove the k-th player while moving around the circle. Maintain an index that advances by k - 1 positions each round using modulo arithmetic to wrap around the list. After removing a player, the next count continues from the same index because the circle shrinks. The process continues until only one element remains in the list. This solution is intuitive and mirrors the real game mechanics, making it useful for understanding the elimination process. However, list deletions and repeated traversal lead to O(n*k) time in the worst case.

The implementation often uses a dynamic array or queue structure from the array family. Each iteration performs an index calculation and removal, which shifts remaining elements. For large inputs, this repeated removal becomes the main bottleneck.

Approach 2: Mathematical Solution using Josephus Problem (O(n) time, O(1) space)

The circular elimination follows a well-known recurrence called the Josephus formula. Instead of simulating removals, compute the survivor position incrementally. If f(n, k) represents the winner among n players, the recurrence is:

f(n, k) = (f(n - 1, k) + k) % n

Start with the base case f(1, k) = 0 (0-indexed). Iterate from 2 to n, updating the survivor index each step. The final answer is converted to 1-indexed by adding 1. This approach eliminates the need for explicit simulation and avoids repeated deletions. The logic can also be written using recursion, though the iterative form avoids stack overhead.

This mathematical insight reduces the problem to a simple loop and constant memory usage. The algorithm runs in O(n) time and O(1) space, which is optimal for this problem.

Recommended for interviews: Start with the simulation idea because it shows you understand the circular elimination process. Then derive or mention the Josephus recurrence to reach the O(n) solution. Interviewers typically expect the mathematical approach since it demonstrates deeper algorithmic reasoning beyond straightforward simulation.

Approach 1: Approach 1: Simulating the Process with a List

This approach simulates the game using a list (or array) to represent the friends. We start from the first friend and iteratively remove the k-th friend (considering the wrap around for the circle) until only one friend remains. The advantage of this method is its simplicity and straightforwardness, although it might not be the most efficient solution.

Steps:

  1. Initialize a list of friends.
  2. Start from the first friend.
  3. In each iteration, compute the index of the friend to be eliminated.
  4. Remove the friend from the list.
  5. Continue the process until only one friend is left.

This C code defines a function `findTheWinner` that constructs an array `friends` representing the circle and uses a loop to simulate the elimination process. The `index` keeps track of the current position, and friends are removed by shifting elements.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), as each friend removal involves an O(n) operation in the worst case.
Space Complexity: O(n), due to the additional array used to represent friends.

Try this approach in the editor →

Approach 2: Approach 2: Mathematical Solution using Josephus Problem

The problem can be reduced to a well-known mathematical problem called the Josephus Problem. Instead of simulating each elimination, we derive the position of the winner directly using a mathematical formula.

The formula for the winner's position in the Josephus problem (0-indexed) is given by:

f(n) = (f(n-1) + k) % n for n > 1, and f(1) = 0 as the base case.

To get the result in 1-indexing that our problem requires, we add 1 to the result.

This C implementation uses the iterative formula for the Josephus Problem to find the winner efficiently without simulating each elimination.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), iterating once for each friend.
Space Complexity: O(1), using a constant amount of space.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Simulation

Code

TypeScriptJavaScript

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Simulating the Process with a List

Time Complexity: O(n^2), as each friend removal involves an O(n) operation in the worst case.
Space Complexity: O(n), due to the additional array used to represent friends.

Approach 2: Mathematical Solution using Josephus Problem

Time Complexity: O(n), iterating once for each friend.
Space Complexity: O(1), using a constant amount of space.

Default Approach—
Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulating the Process with a ListO(n*k)O(n)When you want a straightforward implementation that mirrors the game process
Mathematical Josephus SolutionO(n)O(1)Best for interviews and large inputs where simulation would be slower

Video Solution

Find the Winner of the Circular Game - Leetcode 1823 - Python • NeetCodeIO • 19,361 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Winner of the Circular Game easy or hard?
The problem is rated Medium because the straightforward simulation is simple but inefficient, while the optimal solution requires recognizing the Josephus pattern. Candidates who know the recurrence can solve it quickly with a short O(n) implementation.
How to solve Find the Winner of the Circular Game in O(n)?
Use the Josephus recurrence relation. Start with a base survivor index of 0 when n = 1, then iterate from 2 to n and update the index with (result + k) % i. After finishing the loop, add 1 to convert the 0‑indexed result to the player label.
Find the Winner of the Circular Game Python or Java solution?
Python and Java implementations usually include two variants: a simulation using a list or queue, and the optimal Josephus formula. The Python version often uses list indexing with modulo, while Java solutions typically implement the recurrence in a simple loop for O(n) time.
What is the best approach for Find the Winner of the Circular Game?
The optimal approach uses the Josephus problem recurrence. Instead of simulating removals, compute the survivor index using f(n, k) = (f(n − 1, k) + k) % n. This method runs in O(n) time and O(1) space, making it significantly more efficient than repeatedly deleting elements from a list.
What data structure is used in Find the Winner of the Circular Game?
The simulation solution commonly uses a dynamic array or queue to represent the circle of players. Each round removes the k-th element and continues counting from the next position. The optimized Josephus solution does not require any data structure beyond a few integer variables.
What is the time complexity of Find the Winner of the Circular Game?
The simulation approach typically runs in O(n*k) time because the algorithm repeatedly moves through the circular list and removes elements. The optimized Josephus mathematical solution runs in O(n) time with O(1) extra space by iteratively computing the surviving position.
Is Find the Winner of the Circular Game asked at Google, Amazon, or Meta?
Josephus-style elimination problems frequently appear in interviews at large tech companies including Amazon, Google, and Meta. Interviewers often use them to test understanding of mathematical recurrences, circular indexing, and simulation techniques.

Ready to solve this problem?

Practice Find the Winner of the Circular Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays