Medium · simulation
The Josephus Circle
The rules are cruelly simple: count k alive people starting from the current one, the k-th leaves the circle, and counting resumes with the person after them. No formula, no cleverness — just faithful bookkeeping, which is exactly what a computer is for.
At a glanceKeep <code>alive[n]</code> and a cursor. Walk the circle counting alive people; on the k-th, print, mark dead, and restart counting at the next position (<code>cur = (cur + 1) % n</code>).
Problem
Input: One line with n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 100). People are numbered 1..n; counting starts at person 1 and the k-th alive person is eliminated, repeatedly, until none remain.
Output: The elimination order: n numbers separated by single spaces (the last one is the survivor).
Samples:
| Input | Output |
|---|---|
5 3 | 3 1 5 2 4 |
1 7 | 1 |
With n = 5, k = 3: count 1, 2, 3 — person 3 leaves. Resume at 4: 4, 5, 1 — person 1 leaves. Resume at 2: 2, 4, 5 — person 5 leaves. Resume at 2 again (now 2, 4 alive): 2, 4, 2 — person 2 leaves; 4 is the survivor.
Your solution
Custom input for "Run my input"
Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.
Stuck? Hints
Hint 1 — The circle is just modulo
Person i lives at index i−1, and the next position after index n−1 is index 0: cur = (cur + 1) % n. That one expression is the entire circle. Every circular problem you will ever meet — ring buffers, round-robin scheduling — is this same modulo wearing different clothes.
Hint 2 — Count only the living
The inner walk must skip dead positions without spending a count: if (alive[cur]) { count++; ... } then advance. If dead positions consumed counts, eliminations repeat and the order self-destructs by the third round — the judge's sample catches it immediately.
Hint 3 — Counting resumes after the fallen
After eliminating person p, the next count starts at the person after p — with your cursor pointing at p, that is one more cur = (cur + 1) % n before the next round. Starting the count at p again happens to give the same answer when p's neighbours are alive... and silently diverges later. Trace the sample by hand before trusting it.
Solution (try it first!)
#include <iostream>
using namespace std;
bool alive[105];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) alive[i] = true;
int cur = 0;
for (int round = 0; round < n; round++) {
int count = 0;
while (true) {
if (alive[cur]) {
count++;
if (count == k) break;
}
cur = (cur + 1) % n;
}
alive[cur] = false;
cout << cur + 1;
if (round < n - 1) cout << " ";
cur = (cur + 1) % n;
}
cout << endl;
return 0;
}Two bookkeeping ideas carried this whole problem: a boolean array as the ground truth of who remains, and modulo as the circle. Both are workhorses — the same alive[] pattern drives sieve marking in Count the Primes, and the same modulo drives ring buffers. When a story can be replayed step by step, simulation is not the naive choice; it is the verifiable one.
Deep dive
Why this works
No closed form is needed at this scale — the rules are simple enough to replay faithfully. An alive[] boolean array is the ground truth of who remains; the circle is (cur + 1) % n; counting counts only alive positions. Simulation turns a puzzle into bookkeeping, and bookkeeping cannot argue with the judge.
The cost
O(n × k) worst case (each round walks up to k positions), O(n) space — for n = 100, k = 100 that is 10,000 steps, trivial.
Where it goes wrong
- Counting dead positions as alive: eliminations start repeating and the order self-destructs — visible from the third elimination in the sample.
- Restarting the count at the person just eliminated instead of the next one: coincidentally correct for a round or two, silently wrong afterwards.
- Off-by-one on k: 'every k-th' includes the starter (k = 1 eliminates the current person every round, giving 1 2 … n).
Next step
The alive[] bookkeeping is the same machine that marks the sieve in Count the Primes; the modulo walk is the ring buffer's heart. Another faithful step-by-step process you already own: Bubble Sort.
Two things to remember
- A circle is an array plus (cur + 1) % n — nothing more.
- Simulation is the honest tool when rules are simple and formulas are not in reach.
🐞 This version fails — open it and try
Counts dead people too — eliminations repeat and the order self-destructs
#include <iostream>
using namespace std;
bool alive[105];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) alive[i] = true;
int cur = 0;
for (int round = 0; round < n; round++) {
for (int step = 0; step < k; step++) { // bug: no alive check
cur = (cur + 1) % n;
}
cur = (cur - 1 + n) % n; // compensate — still wrong
alive[cur] = false;
cout << cur + 1;
if (round < n - 1) cout << " ";
cur = (cur + 1) % n;
}
cout << endl;
return 0;
}