Find the Winner of the Circular Game

Medium
1081.

Find the Winner of the Circular Game

Find the Winner of the Circular Game is a medium coding problem on arrays, math and simulation, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findTheWinner = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    This is the Josephus problem.

  2. Hint 2

    Solve it for a circle of i people from the answer for i - 1: after one elimination the circle is the same shape, just rotated by k.

  3. Hint 3

    f(1) = 0 and f(i) = (f(i-1) + k) mod i, with the answer being f(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

  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

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Recursion