Find the Winner of the Circular Game Solution

The problem

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 i^th friend brings you to the (i+1)^th friend for 1 <= i < n, and moving clockwise from the n^th friend brings you to the 1^st friend.

The rules of the game are as follows:

Start at the 1^st friend.
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.
The last friend you counted leaves the circle and loses the game.
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.
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:

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

Python

def find_the_winner(n, k):
    friends = list(range(1, n + 1))
    index = 0
    while len(friends) > 1:
        index = (index + k - 1) % len(friends)
        friends.pop(index)
    return friends[0]

print("Winner:", find_the_winner(5, 2))
print("Winner:", find_the_winner(6, 5))

Java

import java.util.LinkedList;
import java.util.List;

public class CircularGame {
    public static int findTheWinner(int n, int k) {
        List<Integer> friends = new LinkedList<>();
        for (int i = 1; i <= n; i++) friends.add(i);
        int index = 0;
        while (friends.size() > 1) {
            index = (index + k - 1) % friends.size();
            friends.remove(index);
        }
        return friends.get(0);
    }

    public static void main(String[] args) {
        System.out.println("Winner: " + findTheWinner(5, 2));
        System.out.println("Winner: " + findTheWinner(6, 5));
    }
}

C++

#include <iostream>
#include <list>

int findTheWinner(int n, int k) {
    std::list<int> friends;
    for (int i = 1; i <= n; ++i) friends.push_back(i);
    auto it = friends.begin();
    while (friends.size() > 1) {
        for (int i = 1; i < k; ++i) {
            ++it;
            if (it == friends.end()) it = friends.begin();
        }
        it = friends.erase(it);
        if (it == friends.end()) it = friends.begin();
    }
    return friends.front();
}

int main() {
    std::cout << "Winner: " << findTheWinner(5, 2) << std::endl;
    std::cout << "Winner: " << findTheWinner(6, 5) << std::endl;
    return 0;
}

JavaScript

function findTheWinner(n, k) {
    let friends = Array.from({ length: n }, (_, i) => i + 1);
    let index = 0;
    while (friends.length > 1) {
        index = (index + k - 1) % friends.length;
        friends.splice(index, 1);
    }
    return friends[0];
}

console.log("Winner:", findTheWinner(5, 2));
console.log("Winner:", findTheWinner(6, 5));

#include <stdio.h>
#include <stdlib.h>

int findTheWinner(int n, int k) {
    int *friends = (int*)malloc(n*sizeof(int));
    for (int i = 0; i < n; ++i) friends[i] = i+1;
    int index = 0, remaining = n;
    while (remaining > 1) {
        index = (index + k - 1) % remaining;
        for (int j = index; j < remaining - 1; ++j) friends[j] = friends[j + 1];
        remaining--;
    }
    int winner = friends[0];
    free(friends);
    return winner;
}

int main() {
    printf("Winner: %d\n", findTheWinner(5, 2));
    printf("Winner: %d\n", findTheWinner(6, 5));
    return 0;
}

using System;
using System.Collections.Generic;

class CircularGame {
    public static int FindTheWinner(int n, int k) {
        List<int> friends = new List<int>();
        for (int i = 1; i <= n; i++) friends.Add(i);
        int index = 0;
        while (friends.Count > 1) {
            index = (index + k - 1) % friends.Count;
            friends.RemoveAt(index);
        }
        return friends[0];
    }

    static void Main() {
        Console.WriteLine("Winner: " + FindTheWinner(5, 2));
        Console.WriteLine("Winner: " + FindTheWinner(6, 5));
    }
}

The Python solution creates a list of friends and eliminates every k-th friend using the `pop` method, recalculating the index for each elimination.

Complexity

Time Complexity: O(n^2), as the list operations make it similar to other solutions.
Space Complexity: O(n), for maintaining the list of 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.

Python

def find_the_winner(n, k):
    winner = 0
    for i in range(2, n + 1):
        winner = (winner + k) % i
    return winner + 1

print("Winner:", find_the_winner(5, 2))
print("Winner:", find_the_winner(6, 5))

Java

public class CircularGame {
    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;
    }

    public static void main(String[] args) {
        System.out.println("Winner: " + findTheWinner(5, 2));
        System.out.println("Winner: " + findTheWinner(6, 5));
    }
}

C++

#include <iostream>

int findTheWinner(int n, int k) {
    int winner = 0;
    for (int i = 2; i <= n; ++i) {
        winner = (winner + k) % i;
    }
    return winner + 1;
}

int main() {
    std::cout << "Winner: " << findTheWinner(5, 2) << std::endl;
    std::cout << "Winner: " << findTheWinner(6, 5) << std::endl;
    return 0;
}

JavaScript

function findTheWinner(n, k) {
    let winner = 0;
    for (let i = 2; i <= n; i++) {
        winner = (winner + k) % i;
    }
    return winner + 1;
}

console.log("Winner:", findTheWinner(5, 2));
console.log("Winner:", findTheWinner(6, 5));

#include <stdio.h>

int findTheWinner(int n, int k) {
    int winner = 0; // Josephus problem base case for 1 person
    for (int i = 2; i <= n; ++i) {
        winner = (winner + k) % i;
    }
    return winner + 1;
}

int main() {
    printf("Winner: %d\n", findTheWinner(5, 2));
    printf("Winner: %d\n", findTheWinner(6, 5));
    return 0;
}

using System;

class CircularGame {
    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;
    }

    static void Main() {
        Console.WriteLine("Winner: " + FindTheWinner(5, 2));
        Console.WriteLine("Winner: " + FindTheWinner(6, 5));
    }
}

The Python code succinctly finds the winning friend position using the direct formula to solve the Josephus problem.

Complexity

Time Complexity: O(n), iteratively applying the formula for each i.
Space Complexity: O(1), with no additional storage requirements aside from a few variables.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function findTheWinner(n: number, k: number): number {
    if (n === 1) {
        return 1;
    }
    const ans = (k + findTheWinner(n - 1, k)) % n;
    return ans ? ans : n;
}

func findTheWinner(n int, k int) int {
	if n == 1 {
		return 1
	}
	ans := (findTheWinner(n-1, k) + k) % n
	if ans == 0 {
		return n
	}
	return ans
}

Rust

impl Solution {
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        if n == 1 {
            return 1;
        }
        let mut ans = (k + Solution::find_the_winner(n - 1, k)) % n;
        return if ans == 0 { n } else { ans };
    }
}

Try this approach in the editor

Approach 4: Simulation

TypeScript

function findTheWinner(n: number, k: number): number {
    const arr = Array.from({ length: n }, (_, i) => i + 1);
    let i = 0;

    while (arr.length > 1) {
        i = (i + k - 1) % arr.length;
        arr.splice(i, 1);
    }

    return arr[0];
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Simulating the Process with a List	Time Complexity: O(n^2), as the list operations make it similar to other solutions. Space Complexity: O(n), for maintaining the list of friends.
Approach 2: Mathematical Solution using Josephus Problem	Time Complexity: O(n), iteratively applying the formula for each i. Space Complexity: O(1), with no additional storage requirements aside from a few variables.
Default Approach	–
Simulation	–

Complexity analysis

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

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.

Find the Winner of the Circular Game solution and explanation

The problem

Approach overview

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

Approach 2: Approach 2: Mathematical Solution using Josephus Problem

Approach 3: Default Approach

Approach 4: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Winner of the Circular Game solution and explanation

The problem

Approach overview

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

Approach 2: Approach 2: Mathematical Solution using Josephus Problem

Approach 3: Default Approach

Approach 4: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems