Skip to content

1823. Find the Winner of the Circular Game 👍

Approach 1: Simulation

  • 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) {
    // friends[i] := true if i-th friend is left
    vector<bool> friends(n);

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

    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(friends.begin(), friends.end(), [](int f) { return !f; });
    return distance(friends.begin(), 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) {
    // friends[i] := true if i-th friend is left
    boolean[] friends = new boolean[n];

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

    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' index

    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

Approach 2: Recursive Josephus

  • Time: $O(n)$
  • 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
23
24
25
class Solution {
 public:
  int findTheWinner(int n, int k) {
    // Converts back to 1-indexed.
    return f(n, k) + 1;
  }

  // e.g. n = 4, k = 2.
  // By using 0-indexed notation, we have the following circle:
  //
  // 0 -> 1 -> 2 -> 3 -> 0
  //      x
  //           0 -> 1 -> 2 -> 0
  //
  // After the first round, 1 is removed.
  // So, 2 becomes 0, 3 becomes 1, and 0 becomes 2.
  // Let's denote that oldIndex = f(n, k) and newIndex = f(n - 1, k).
  // By observation, we know f(n, k) = (f(n - 1, k) + k) % n.
 private:
  int f(int n, int k) {
    if (n == 1)
      return 0;
    return (f(n - 1, k) + k) % n;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int findTheWinner(int n, int k) {
    // Converts back to 1-indexed.
    return f(n, k) + 1;
  }

  // e.g. n = 4, k = 2.
  // By using 0-indexed notation, we have the following circle:
  //
  // 0 -> 1 -> 2 -> 3 -> 0
  //      x
  //           0 -> 1 -> 2 -> 0
  //
  // After the first round, 1 is removed.
  // So, 2 becomes 0, 3 becomes 1, and 0 becomes 2.
  // Let's denote that oldIndex = f(n, k) and newIndex = f(n - 1, k).
  // By observation, we know f(n, k) = (f(n - 1, k) + k) % n.
  private int f(int n, int k) {
    if (n == 1)
      return 0;
    return (f(n - 1, k) + k) % n;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def findTheWinner(self, n: int, k: int) -> int:
    # e.g. n = 4, k = 2.
    # By using 0-indexed notation, we have the following circle:
    #
    # 0 -> 1 -> 2 -> 3 -> 0
    #      x
    #           0 -> 1 -> 2 -> 0
    #
    # After the first round, 1 is removed.
    # So, 2 becomes 0, 3 becomes 1, and 0 becomes 2.
    # Let's denote that oldIndex = f(n, k) and newIndex = f(n - 1, k).
    # By observation, we know f(n, k) = (f(n - 1, k) + k) % n.
    def f(n: int, k: int) -> int:
      if n == 1:
        return 0
      return (f(n - 1, k) + k) % n

    # Converts back to 1-indexed.
    return f(n, k) + 1

Approach 3: Iterative Josephus

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int findTheWinner(int n, int k) {
    // Converts back to 1-indexed.
    return f(n, k) + 1;
  }

  // e.g. n = 4, k = 2.
  // By using 0-indexed notation, we have the following circle:
  //
  // 0 -> 1 -> 2 -> 3 -> 0
  //      x
  //           0 -> 1 -> 2 -> 0
  //
  // After the first round, 1 is removed.
  // So, 2 becomes 0, 3 becomes 1, and 0 becomes 2.
  // Let's denote that oldIndex = f(n, k) and newIndex = f(n - 1, k).
  // By observation, we know f(n, k) = (f(n - 1, k) + k) % n.
 private:
  int f(int n, int k) {
    int ans = 0;  // f(1, k)
    // Computes f(i, k) based on f(i - 1, k).
    for (int i = 2; i <= n; ++i)
      ans = (ans + k) % i;
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int findTheWinner(int n, int k) {
    // Converts back to 1-indexed.
    return f(n, k) + 1;
  }

  // e.g. n = 4, k = 2.
  // By using 0-indexed notation, we have the following circle:
  //
  // 0 -> 1 -> 2 -> 3 -> 0
  //      x
  //           0 -> 1 -> 2 -> 0
  //
  // After the first round, 1 is removed.
  // So, 2 becomes 0, 3 becomes 1, and 0 becomes 2.
  // Let's denote that oldIndex = f(n, k) and newIndex = f(n - 1, k).
  // By observation, we know f(n, k) = (f(n - 1, k) + k) % n.
  private int f(int n, int k) {
    int ans = 0; // f(1, k)
    // Computes f(i, k) based on f(i - 1, k).
    for (int i = 2; i <= n; ++i)
      ans = (ans + k) % i;
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def findTheWinner(self, n: int, k: int) -> int:
    # e.g. n = 4, k = 2.
    # By using 0-indexed notation, we have the following circle:
    #
    # 0 -> 1 -> 2 -> 3 -> 0
    #      x
    #           0 -> 1 -> 2 -> 0
    #
    # After the first round, 1 is removed.
    # So, 2 becomes 0, 3 becomes 1, and 0 becomes 2.
    # Let's denote that oldIndex = f(n, k) and newIndex = f(n - 1, k).
    # By observation, we know f(n, k) = (f(n - 1, k) + k) % n.
    def f(n: int, k: int) -> int:
      ans = 0  # f(1, k)
      # Computes f(i, k) based on f(i - 1, k).
      for i in range(2, n + 1):
        ans = (ans + k) % i
      return ans

    # Converts back to 1-indexed.
    return f(n, k) + 1