⚡Flashcard Drill➔
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

  1. This is the Josephus problem. Let f(i) be the 0-indexed winner among i people; then f(1) = 0.
  2. After one elimination the circle has i - 1 people, but the counting start shifts by k, giving f(i) = (f(i - 1) + k) % i.
  3. Iterate the recurrence from i = 2 up to n in O(n) time.
  4. 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 is i, so the modulus is i.
  • Initialising res to 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems