Leetcode 1823. Find the Winner of the Circular Game Solution

Problem Explanation

There are n friends playing a game, sitting in a circle. They are numbered from 1 to n in clockwise order. The game has the following rules:

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.

The goal is to determine the winner of the game given the number of friends n and an integer k.

Approach

We can use a vector (or an array) to keep track of which friends are still in the game. We'll use a boolean vector of size n, where friends[i] is true if the i-th friend is out of the game, and false otherwise. Then, we can use a while loop to keep playing the game until only one friend is left.

During each iteration of the loop, we'll move the pointer by k positions clockwise, skipping friends who have already left the game. Once we've reached the next friend to be removed from the game, we mark their position in the friends vector as true, and decrement the friends count. We'll repeat this process until only one friend is left.

Finally, we can use the find_if function from the standard library to find the index of the remaining friend, and return their number (index + 1).

Example

Let's walk through an example with n = 5 and k = 2.

1. Initially, the friends vector is [false, false, false, false, false], and the pointer is at position 0 (friend 1).
2. We move the pointer 2 positions clockwise, skipping friends that are already out of the game. The pointer is now at position 1 (friend 2).
3. We mark friend 2 as out of the game, and decrement the friends count: [false, true, false, false, false], friends count is 4.
4. We move the pointer 2 positions clockwise from friend 2, skipping friends that are already out of the game. The pointer is now at position 3 (friend 4).
5. We mark friend 4 as out of the game, and decrement the friends count: [false, true, false, true, false], friends count is 3.
6. We move the pointer 2 positions clockwise from friend 4, skipping friend 2 who is already out of the game. The pointer is now at position 0 (friend 1).
7. We mark friend 1 as out of the game, and decrement the friends count: [true, true, false, true, false], friends count is 2.
8. We move the pointer 2 positions clockwise from friend 1, skipping friend 4 who is already out of the game. The pointer is now at position 4 (friend 5).
9. We mark friend 5 as out of the game, and decrement the friends count: [true, true, false, true, true], friends count is 1.

At this point, only friend 3 is left in the game, so they are the winner.

C++ Solution

1#include <algorithm>
2#include <vector>
3
4class Solution {
5 public:
6  int findTheWinner(int n, int k) {
7    // friends[i] := true if i-th friend is left.
8    std::vector<bool> friends(n);
9
10    int friendCount = n;
11    int fp = 0;  // friends' pointer
12
13    while (friendCount > 1) {
14      for (int i = 0; i < k; ++i, ++fp)
15        while (friends[fp % n])  // The friend is not there.
16          ++fp;                  // Point to the next one.
17      friends[(fp - 1) % n] = true;
18      --friendCount;
19    }
20
21    // Find the remaining friend and return their number (index + 1)
22    const auto it =
23        std::find_if(begin(friends), end(friends), [](int f) { return !f; });
24    return std::distance(begin(friends), it) + 1;
25  }
26};

Python Solution

1class Solution:
2    def findTheWinner(self, n: int, k: int) -> int:
3        friends = [False] * n
4        
5        friend_count = n
6        fp = 0
7        
8        while friend_count > 1:
9            i = 0
10            while i < k:
11                if not friends[fp % n]:
12                    i += 1
13                fp += 1
14            friends[(fp - 1) % n] = True
15            friend_count -= 1
16        
17        return friends.index(False) + 1

Java Solution

1import java.util.ArrayList;
2
3public class Solution {
4    public int findTheWinner(int n, int k) {
5        ArrayList<Boolean> friends = new ArrayList<Boolean>(n);
6        for(int i = 0; i < n; i++)
7            friends.add(false);
8        
9        int friendCount = n;
10        int fp = 0;
11        
12        while(friendCount > 1) {
13            int i;
14            for (i = 0; i < k; fp++)
15                if (!friends.get(fp % n)) i++;
16            friends.set((fp - 1) % n, true);
17            friendCount--;
18        }
19        
20        for (int i = 0; i < n; i++)
21            if (!friends.get(i)) return i + 1;
22        return -1;
23    }
24}

JavaScript Solution

1class Solution {
2  findTheWinner(n, k) {
3    const friends = new Array(n).fill(false);
4
5    let friendCount = n;
6    let fp = 0;
7
8    while (friendCount > 1) {
9      let i = 0;
10      while (i < k) {
11        if (!friends[fp % n]) i++;
12        fp++;
13      }
14      friends[(fp - 1) % n] = true;
15      friendCount--;
16    }
17
18    return friends.findIndex(f => !f) + 1;
19  }
20}
21
22// Usage
23const solution = new Solution();
24console.log(solution.findTheWinner(5, 2)); // Output: 3

C# Solution

1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int FindTheWinner(int n, int k) {
6        List<bool> friends = new List<bool>(new bool[n]);
7        
8        int friendCount = n;
9        int fp = 0;
10        
11        while(friendCount > 1) {
12            int i;
13            for (i = 0; i < k; fp++)
14                if (!friends[fp % n]) i++;
15            friends[(fp - 1) % n] = true;
16            friendCount--;
17        }
18        
19        return friends.IndexOf(false) + 1;
20    }
21}
22```## Conclusion
23
24To determine the winner of the game, given the number of friends `n` and an integer `k`, we can follow these general steps:
25
261. Create a boolean vector or array to keep track of which friends are still in the game.
272. Use a while loop to keep playing the game until only one friend is left.
283. During each iteration, move the pointer by `k` positions clockwise, skipping friends who have already left the game.
294. Mark the remaining friend as out of the game and decrement the friend count.
305. Find the index of the remaining friend and return their number (index + 1).
31
32We provided C++, Python, Java, JavaScript, and C# solutions that follow these steps above. Each solution first initializes a boolean vector or array that represents whether each friend is in or out of the game. Then, we iteratively move clockwise and mark friends as out of the game until only one friend remains. Finally, we find the index of the remaining friend and return their number.