MediumArrayMathRecursionQueueSimulationUpdated Sep 2026

1823. Find the Winner of the Circular Game

Asked at Goldman Sachs

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

There are n friends sitting in a circle, numbered 1 to n clockwise. Counting starts at friend 1. On each turn you count k friends clockwise, including the friend you start on, and the last friend you counted is removed from the circle. Counting wraps around, so you may pass the same friends more than once.

If more than one friend is still in the circle, the next turn starts from the friend sitting immediately clockwise of the one who just left. The game ends when only one friend remains, and that friend is the winner.

Given n and k, return the number of the winning friend.

A circle of 5 friends, k = 2

circle12345startCount 1 and 2 starting at friend 1, so friend 2 isremoved first.circle1345startNext start is friend 3; counting 3 and 4 removesfriend 4.circle135startCounting wraps around 5 then 1, so friend 1 leaves.
Counting starts at friend 1 and every 2nd friend counted leaves the circle.

Constraints

  • ●1 <= k <= n <= 500

Examples

Example 1
Inputn = 5, k = 2
Output3
WhyFriends 2, 4, 1 and 5 leave in that order, so friend 3 is the last one sitting.
Example 2
Inputn = 6, k = 5
Output1
WhyThe friends leave in the order 5, 4, 6, 2, 3, which leaves friend 1 as the winner.

Asked At

1 companies
CompanyDifficulty
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

Simulation: put everyone in a queue, rotate k - 1 people to the back, remove the next one, repeat. That is O(n * k) — fine for the constraints but not optimal.

2

Key insight (Josephus): after removing one person from a circle of i, the survivor of the remaining i - 1 people is the same person, just with indices shifted by k.

3

Recurrence with 0-indexed positions: f(1) = 0 and f(i) = (f(i - 1) + k) % i. The answer is f(n) + 1.

4

Compute it iteratively from i = 2 to n — no recursion needed.

5

Walkthrough for n = 5, k = 2: f = 0, (0+2)%2 = 0, (0+2)%3 = 2, (2+2)%4 = 0, (0+2)%5 = 2 -> friend 3.

Optimal Approach

Step 1: pos = 0 (the winner in a circle of 1, 0-indexed).
Step 2: For i from 2 to n: pos = (pos + k) % i.
Step 3: Return pos + 1.

Time: O(n). Space: O(1).

Josephus recurrence, one step at a time

pos = 0 (circle of 1)i = 2: (0+2) % 2 = 0i = 3: (0+2) % 3 = 2i = 4: (2+2) % 4 = 0i = 5: (0+2) % 5 = 2Grow the circle from 1 friend up to n and update thewinner's position each time.f(1) = 0f(i) = (f(i-1) + k) % ianswer = f(n) + 1 = 2 + 1 = 3
pos is the winner's 0-indexed seat in a circle of size i; each new friend shifts it by k.
ComplexityTime O(n)Space O(1)One loop runs n - 1 times with a single arithmetic step each, and only one integer is stored.

What Trips People Up in Real Interviews

1

Removing from the middle of a Python list or Java ArrayList during simulation — each removal is O(n), so the simulation is O(n²).

2

Mixing 0-indexed and 1-indexed positions in the recurrence. Work 0-indexed and add 1 at the end.

3

Presenting the recurrence without explaining the index shift — interviewers usually ask why it works.

4

Starting the loop at i = 1, which applies an extra shift.

Solution Code

O(n) time
def findTheWinner(n, k):
    pos = 0
    for i in range(2, n + 1):
        pos = (pos + k) % i
    return pos + 1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Find the Winner of the Circular Game problem?

Find the Winner of the Circular Game seats `n` friends in a circle and repeatedly removes every `k`-th person until one remains. It is the Josephus problem: simulate with a queue for an `O(n * k)` answer, or use the recurrence for `O(n)` time and `O(1)` space.

How do you solve Find the Winner of the Circular Game?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Find the Winner of the Circular Game?

Find the Winner of the Circular Game is asked at Goldman Sachs. It is a medium difficulty problem.

What are common mistakes on Find the Winner of the Circular Game?
  • Removing from the middle of a Python list or Java ArrayList during simulation — each removal is `O(n)`, so the simulation is `O(n²)`.
  • Mixing 0-indexed and 1-indexed positions in the recurrence. Work 0-indexed and add 1 at the end.
  • Presenting the recurrence without explaining the index shift — interviewers usually ask why it works.
  • Starting the loop at `i = 1`, which applies an extra shift.