NeetCode #932LC-1823MediumMath & Geometry
← Back to All Problems#932 · #1823 · Find the Winner of the Circular Game(找出游戏的获胜者)
📌 Problem Statement & Constraints
n friends numbered 1..n stand in a circle. Counting starts at friend 1; every k-th friend is eliminated and counting resumes from the next friend. Return the number of the last remaining friend. Constraints: 1 <= k <= n <= 500.💡 Core Algorithmic Approaches
- This is the Josephus problem. Let
f(i)be the 0-indexed winner amongipeople; thenf(1) = 0. - After one elimination the circle has
i - 1people, but the counting start shifts byk, givingf(i) = (f(i - 1) + k) % i. - Iterate the recurrence from
i = 2up tonin O(n) time. - Add 1 at the end to convert the 0-indexed result back to the 1-indexed numbering.
💻 Benchmark Python3 Implementation
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
res = 0 # f(1) = 0 (0-indexed)
for i in range(2, n + 1):
res = (res + k) % i # recurrence
return res + 1 # back to 1-indexed⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a single recurrence pass.
💾 Space Complexity
O(1): constant state.
⚠️ Interview Pitfalls & Follow-ups
- Simulating the circle with a list or queue: correct but O(n * k) or O(n) extra space; the recurrence is strictly better.
- Forgetting the final
+ 1: the recurrence yields a 0-indexed position. - Writing
% (i + 1): the current population isi, so the modulus isi. - Initialising
resto 1: the base case is 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.