# Find the Winner of the Circular Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-winner-of-the-circular-game)
Canonical: https://scaleengineer.com/dsa/problems/find-the-winner-of-the-circular-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Array, Queue
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [SoFi](https://scaleengineer.com/companies/sofi), [Zoho](https://scaleengineer.com/companies/zoho), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Groupon](https://scaleengineer.com/companies/groupon)
---
## 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 `ith` friend brings you to the `(i+1)th` friend for `1 <= i < n`, and moving clockwise from the `nth` friend brings you to the `1st` friend.

The rules of the game are as follows:

1. **Start** at the `1st` friend.
2. 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.
3. The last friend you counted leaves the circle and loses the game.
4. 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.
5. 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:**

![](https://assets.glich.co/dsa/find-the-winner-of-the-circular-game/image0.png) 

**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?

# Approaches
## Simulation using a List
This is a straightforward approach that directly simulates the game as described. We use a dynamic list, like an `ArrayList`, to keep track of the friends currently in the circle. In each round, we find and remove the friend who is counted out.
**Time:** O(n^2) - The simulation runs for `n-1` rounds. In each round, removing an element from an `ArrayList` can take up to O(n) time because all subsequent elements must be shifted. · **Space:** O(n) - We need a list to store the `n` friends.
**Pros:** Simple to understand and implement.; Directly models the game's rules.
**Cons:** Inefficient for large `n` due to the costly O(n) removal operation in a list.
### Explanation
The core idea is to use a list to represent the circle of friends. We start with a list containing numbers from 1 to `n`. We also maintain a pointer, `currentIndex`, to know where to start counting in each round. The game proceeds in rounds, with one friend being eliminated in each round. The loop continues as long as there is more than one friend. To find which friend to eliminate, we advance `k-1` steps from `currentIndex`, wrapping around the list using the modulo operator. After removing the friend, the list shrinks, and the element that was to the right of the removed one now occupies its position. This becomes our new `currentIndex` for the next round. Finally, when only one friend is left, they are the winner.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int findTheWinner(int n, int k) {
        List<Integer> friends = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            friends.add(i);
        }

        int currentIndex = 0;
        while (friends.size() > 1) {
            int removalIndex = (currentIndex + k - 1) % friends.size();
            friends.remove(removalIndex);
            // The next starting position is the same as the removal index
            // because the list shifts left.
            currentIndex = removalIndex;
        }

        return friends.get(0);
    }
}
```
### Algorithm
- Initialize a list (e.g., `ArrayList`) with numbers from 1 to `n`.
- Keep track of the starting position for counting in each round, let's call it `currentIndex`, initialized to 0.
- Loop as long as the size of the list is greater than 1.
- In each iteration, calculate the index of the friend to be removed. The formula is `(currentIndex + k - 1) % list.size()`.
- Remove the friend at the calculated index.
- The `currentIndex` for the next round will be the same as the removal index, as the list elements shift to the left after removal.
- After the loop terminates, the list will contain a single element, which is the winner.

## Simulation using a Queue
This approach also simulates the game but uses a more suitable data structure, a queue, to optimize the process. A queue (implemented as a `LinkedList`) allows for efficient removal from the front (O(1)). We simulate the 'counting' by rotating the elements of the queue.
**Time:** O(n * k) - The main loop runs `n-1` times. Inside, we perform `k-1` queue rotations, each taking O(1) time. Thus, the total time is proportional to `n * k`. · **Space:** O(n) - A queue is used to store the `n` friends.
**Pros:** More efficient than the list approach if `k` is small.; Conceptually clean way to handle a circular arrangement.
**Cons:** Performance degrades as `k` increases, becoming O(n^2) in the worst case.; Still requires O(n) auxiliary space.
### Explanation
To avoid the expensive removal operation of the list-based approach, we can use a queue. A queue provides constant time `add` (enqueue) and `poll` (dequeue) operations. We first populate the queue with all `n` friends. The game proceeds in rounds until one friend is left. In each round, instead of moving a pointer, we rotate the queue. To get to the `k`-th person, we dequeue `k-1` people from the front and immediately enqueue them to the back. After these rotations, the person to be eliminated is conveniently at the front of the queue. We can then remove them with a single `poll()` operation. This process is repeated until the queue has only one element, which is the winner.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int findTheWinner(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }

        while (queue.size() > 1) {
            // Move k-1 friends from the front to the back of the queue.
            for (int i = 0; i < k - 1; i++) {
                queue.add(queue.poll());
            }
            // The k-th friend is now at the front, so we remove them.
            queue.poll();
        }

        return queue.peek();
    }
}
```
### Algorithm
- Initialize a queue (e.g., `LinkedList`) and enqueue all friend numbers from 1 to `n`.
- Loop while the queue contains more than one friend.
- To find the `k`-th friend, perform `k-1` rotations. In each rotation, dequeue an element from the front and enqueue it to the back.
- After `k-1` rotations, the friend at the front of the queue is the one to be eliminated. Simply dequeue them.
- Repeat this process until only one friend is left in the queue.
- The last remaining element in the queue is the winner.

## Optimal Mathematical Solution (Josephus Problem)
This problem is a classic variant of the Josephus Problem, which can be solved efficiently using a mathematical recurrence relation. Instead of simulating the entire game, we can directly compute the winner's position. This approach offers the best performance by avoiding simulation altogether and meets the follow-up challenge of linear time and constant space.
**Time:** O(n) - The solution uses a single loop that iterates from 2 to `n`, performing constant time operations inside. · **Space:** O(1) - The iterative solution uses only a few variables, requiring constant extra space.
**Pros:** Optimal solution with linear time and constant space complexity.; Extremely fast for large `n`.
**Cons:** The logic is abstract and less intuitive than direct simulation.; Requires knowledge of the underlying recurrence relation.
### Explanation
The most efficient solution leverages the mathematical properties of the problem. Let's define `f(n, k)` as the position of the winner in a 0-indexed circle of `n` people. When we eliminate the first person (at index `(k-1)%n`), we are left with a smaller problem of `n-1` people. The key insight is to relate the solution of the `n-1` person problem back to the `n` person problem. The winner's position in the `n-1` person circle, `f(n-1, k)`, can be mapped back to the original circle, leading to the recurrence relation: `f(n, k) = (f(n-1, k) + k) % n`. We can solve this iteratively for optimal performance. We start with the solution for one person, `f(1, k) = 0`, and iteratively apply the formula to find the solution for 2, 3, ..., up to `n` people. This avoids recursion and uses constant extra space. The final 0-indexed result is then converted to the 1-indexed friend number required by the problem.

```java
class Solution {
    public int findTheWinner(int n, int k) {
        // The position of the winner in a 0-indexed circle of i people
        // is given by f(i) = (f(i-1) + k) % i.
        int winnerPosition = 0; // Base case: f(1, k) = 0

        // Iteratively compute the winner's position for 2, 3, ..., n people.
        for (int i = 2; i <= n; i++) {
            winnerPosition = (winnerPosition + k) % i;
        }

        // Convert the 0-indexed position to a 1-indexed friend number.
        return winnerPosition + 1;
    }
}
```
### Algorithm
- This problem is a variant of the Josephus Problem, which has a mathematical solution based on a recurrence relation.
- Let `f(n, k)` be the 0-indexed position of the winner with `n` people and step `k`.
- The base case is `f(1, k) = 0`.
- The recurrence relation is `f(n, k) = (f(n-1, k) + k) % n`.
- We can solve this iteratively by starting with the base case for `n=1` and building up the solution to `n`.
- Start with `winner_pos = 0` (for `n=1`).
- Loop from `i = 2` to `n`, updating the position with `winner_pos = (winner_pos + k) % i`.
- The final result is the 0-indexed `winner_pos` converted to a 1-indexed number by adding 1.

# Solutions
### Java

```java
class Solution {
public
  int findTheWinner(int n, int k) {
    if (n == 1) {
      return 1;
    }
    int ans = (findTheWinner(n - 1, k) + k) % n;
    return ans == 0 ? n : ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @param {number} k * @return {number} */ var findTheWinner =
  function (n, k) {
    if (n === 1) {
      return 1;
    }
    const ans = (k + findTheWinner(n - 1, k)) % n;
    return ans ? ans : n;
  };

```

### Python

```python
class Solution:
    def findTheWinner(self, n: int, k: int) -> int: if n == 1: return 1 ans = (k + self . findTheWinner(n - 1, k)) % n return n if ans == 0 else ans

```

### CPP

```cpp
class Solution {
public:
  int findTheWinner(int n, int k) {
    if (n == 1)
      return 1;
    int ans = (findTheWinner(n - 1, k) + k) % n;
    return ans == 0 ? n : ans;
  }
};

```