Josephus problem

O(n²)

The Josephus problem asks: given n people standing in a circle, repeatedly eliminate every k-th person starting from position 1 — who is the last one standing? The classic n=7, k=3 case has a well-known answer of position 4. The simulation maintains an ordered list of surviving people, advances a pointer by k each round, removes that person, and continues until only one remains. The problem appears in combinatorics, computer science puzzles, and has an O(n log n) closed-form solution via a recurrence.

Sequence
Press ▶ to run
Edit the input and press Play

How it works

  1. Place n people numbered 1 to n in a circle
  2. Advance the pointer k positions and eliminate that person
  3. Record the eliminated person and continue from the next position
  4. Repeat until one person remains — that is the survivor

Pseudocode

1josephus(n, k):                       # O(n^2)2  circle = [1, 2, ..., n]3  pos = 04  while len(circle) > 1:5    pos = (pos + k - 1) % len(circle)6    eliminate circle[pos]7    if pos >= len(circle): pos = 08  return circle[0]                    # survivor