Find the Winner of the Circular Game — Problem & Solution
Find the Winner of the Circular Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find the Winner of the Circular Game is a medium coding problem on arrays, math and simulation, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Simulation, Recursion, Queue
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
n friends sit in a circle numbered 1 to n clockwise. Starting at friend 1, count k friends clockwise — including the one you start on — and the k-th leaves the circle. Counting then restarts from the friend immediately after the one who left.
Return the number of the last friend remaining.
Example 1
Input: n = 5, k = 2
Output: 3
Explanation: Friends leave in the order 2, 4, 1, 5.
Example 2
Input: n = 6, k = 5
Output: 1
Example 3
Input: n = 1, k = 1
Output: 1
Constraints
1 <= k <= n <= 500
Hints for Find the Winner of the Circular Game
Hint 1
This is the Josephus problem.
Hint 2
Solve it for a circle of
ipeople from the answer fori - 1: after one elimination the circle is the same shape, just rotated byk.Hint 3
f(1) = 0andf(i) = (f(i-1) + k) mod i, with the answer beingf(n) + 1.
How to solve Find the Winner of the Circular Game
The Josephus recurrence. Working 0-indexed, a circle of one person has the survivor at position 0. Adding a person shifts the survivor's position by k, modulo the new circle size — so f(i) = (f(i-1) + k) mod i. Convert back to 1-indexed at the end.
Approach
- Start
winner = 0, the survivor's 0-based seat in a circle of one. - For
ifrom 2 ton, setwinner = (winner + k) mod i. - Return
winner + 1.
Why it works
After the first elimination in a circle of i, what remains is a circle of i - 1 with the count restarting at a seat k positions along — so the survivor of the smaller circle, shifted by k and wrapped, is the survivor of the larger one. That is the whole recurrence, and it replaces an O(n · k) queue simulation with O(n) arithmetic.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The count includes the friend you start on, which is what makes the shift
kand notk - 1. - The recurrence is 0-based; the answer needs a
+ 1. - The modulus is the current circle size
i, notn.
Reference solution
Python
def findTheWinner(n: int, k: int) -> int:
winner = 0
for i in range(2, n + 1):
winner = (winner + k) % i
return winner + 1Java
public static int findTheWinner(int n, int k) {
int winner = 0;
for (int i = 2; i <= n; i++) winner = (winner + k) % i;
return winner + 1;
}C++
int findTheWinner(int n, int k) {
int winner = 0;
for (int i = 2; i <= n; i++) winner = (winner + k) % i;
return winner + 1;
}JavaScript
var findTheWinner = function(n, k) {
var winner = 0;
for (var i = 2; i <= n; i++) winner = (winner + k) % i;
return winner + 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.