# 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) { // True if i-th friend is left vector 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 

## 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