_1823. Find the Winner of the Circular Game.md

1823. Find the Winner of the Circular Game

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 08, 2024

Last updated : July 08, 2024

---

Related Topics : Array, Math, Recursion, Queue, Simulation

Acceptance Rate : 81.95 %

---

Solutions

• m1823 v1 Daily O(n^2).py
• m1823 v2 Daily O(n) Recursive Josephus Problem.py
• m1823 v2.c
• m1823 v2.cpp
• m1823 v2.java
• m1823 v2.js

Python

m1823 v1 Daily O(n^2).py

# n^2 comes from popping being an O(n) operation for a list
# This could be improved using a deque where we keep adding the 
# popped elements until we reach a removal case.

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        curr = list(range(1, n + 1))
        indx = k - 1
        while len(curr) > 1 :
            curr.pop(indx)
            indx = (indx + k - 1) % len(curr)
        
        return curr[0]

m1823 v2 Daily O(n) Recursive Josephus Problem.py

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

C

m1823 v2.c

int findTheWinner(int n, int k) {
    return (n == 1) ? 1 : (1 + (findTheWinner(n - 1, k) + k - 1) % n);
}

C++

m1823 v2.cpp

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

Java

m1823 v2.java

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

JavaScript

m1823 v2.js

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