Skip to content

1823. Find the Winner of the Circular Game 👍

  • Time: $O(nk)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int findTheWinner(int n, int k) {
    // true if i-th friend is left
    vector<bool> friends(n);

    int friendCount = n;
    int fp = 0;  // friends' pointer

    while (friendCount > 1) {
      for (int i = 0; i < k; ++i, ++fp)
        while (friends[fp % n])  // the friend is not there
          ++fp;                  // point to the next one
      friends[(fp - 1) % n] = true;
      --friendCount;
    }

    const auto it =
        find_if(begin(friends), end(friends), [](int f) { return !f; });
    return distance(begin(friends), it) + 1;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int findTheWinner(int n, int k) {
    // true if i-th friend is left
    boolean[] friends = new boolean[n];

    int friendCount = n;
    int fp = n; // friends' pointer

    while (friendCount > 1) {
      for (int i = 0; i < k; ++i, ++fp)
        while (friends[fp % n]) // the friend is not there
          ++fp;                 // point to the next one
      friends[(fp - 1) % n] = true;
      --friendCount;
    }

    for (fp = 0; friends[fp]; ++fp)
      ;
    return fp + 1;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def findTheWinner(self, n: int, k: int) -> int:
    # true if i-th friend is left
    friends = [False] * n

    friendCount = n
    fp = 0  # friends' pointer

    while friendCount > 1:
      for _ in range(k):
        while friends[fp % n]:  # the friend is not there
          fp += 1  # point to the next one
        fp += 1
      friends[(fp - 1) % n] = True
      friendCount -= 1

    fp = 0
    while friends[fp]:
      fp += 1

    return fp + 1