Get started

Find the Winner of the Circular Game — Medium Problem & Solution

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…

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

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

  1. Start winner = 0, the survivor's 0-based seat in a circle of one.
  2. For i from 2 to n, set winner = (winner + k) mod i.
  3. 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 k and not k - 1.
  • The recurrence is 0-based; the answer needs a + 1.
  • The modulus is the current circle size i, not n.

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 + 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue