1823. Find the Winner of the Circular Game - Detailed Explanation
Problem Statement
You have n friends numbered from 1 to n playing a game in a circle. Starting from friend 1, they count off and every time the count reaches k, that friend is eliminated from the circle. The counting then resumes from the next friend. This continues until only one friend remains, and you must return the winner’s number.
Examples
1.
Input
n = 5, k = 2
Output
3
Explanation
Elimination order is [2,4,1,5], so 3 is last remaining
-
Input
n = 6, k = 5
Output
1
Explanation
Elimination order is [5,4,6,2,3], so 1 is last remaining -
Input
n = 7, k = 3
Output
4
Explanation
Elimination order is [3,6,2,7,5,1], so 4 is last remaining
Constraints
- 1 ≤ k ≤ n ≤ 500
- All friends are numbered uniquely from 1 to n
Hints
- Think about how you would simulate the process with a list or queue and remove every kᵗʰ element until one remains
- There is a famous recurrence (Josephus problem) that computes the survivor position in O(n) time
Approaches
Brute Force Simulation
Simulate the circle using a list (or linked list) and repeatedly remove the kᵗʰ friend.
Explanation
- Maintain a zero‑indexed list of players [1,2,…,n]
- Keep a current index
idx = 0 - While more than one player remains:
- Move
idx = (idx + k - 1) % size - Remove the element at
idx
- Move
- Return the last remaining element
Step‑by‑step Walkthrough
For n=5, k=2
- Start list [1,2,3,4,5], idx=0
- Remove at (0+2−1)%5=1 → remove 2 → [1,3,4,5], idx=1
- Remove at (1+2−1)%4=2 → remove 4 → [1,3,5], idx=2
- Remove at (2+2−1)%3=0 → remove 1 → [3,5], idx=0
- Remove at (0+2−1)%2=1 → remove 5 → [3]
Visual Example
[1,2,3,4,5] → remove 2 → [1,3,4,5]
[1,3,4,5] → remove 4 → [1,3,5]
[1,3,5] → remove 1 → [3,5]
[3,5] → remove 5 → [3]
Python Code
Java Code
Complexity Analysis
- Time O(n·m) where each removal from an ArrayList costs O(n) in the worst case → O(n²) overall
- Space O(n) for the list
Mathematical Solution using Josephus Formula
Use the recursive relation:
J(1, k) = 0
J(n, k) = (J(n-1, k) + k) % n
The winner’s position in 1-based indexing is J(n, k) + 1.
Explanation
J(i, k)gives the index (0-based) of the winner among i people- Build up from 1 to n
Step‑by‑step Walkthrough
For n=5, k=2
- J(1)=0
- J(2)=(0+2)%2=0
- J(3)=(0+2)%3=2
- J(4)=(2+2)%4=0
- J(5)=(0+2)%5=2 → winner = 2+1 = 3
Visual Example
i=1 → 0
i=2 → 0
i=3 → 2
i=4 → 0
i=5 → 2 (so friend 3)
Python Code
Java Code
Complexity Analysis
- Time O(n)
- Space O(1)
Common Mistakes
Off‑by‑one in indexing
For simulation, forgetting to subtract 1 before modulus
Removing from wrong index
Using idx = (idx + k) % size instead of k-1 shift
Forgetting 1‑based conversion
After computing 0‑based result, not adding 1
Edge Cases
- n = 1 → always return 1
- k = 1 → last friend is n
- Large k > n → formula handles via modulus
Alternative Variations
- Vary elimination step (e.g., every mᵗʰ in reverse)
- Start counting from arbitrary position
- Two pointers linked list simulation
Related Problems
GET YOUR FREE
Coding Questions Catalog
$197
$78
$78
