DSA SheetEasy
EditorialPractice

RECURSION & BACKTRACKING › RECURSION PROBLEMS

Josephus Problem

EasyEditorial · 7 minGenerated by gpt-5.6-luna · Aug 27

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe survivor position is easier to preserve than the removal order

Directly removing people from a circle forces you to maintain the remaining order and repeatedly find the next position. With n as large as 1,000,000, that simulation can spend too much time shifting or searching. The useful observation is that you do not need the entire removal order; you only need the final survivor's position.

Use zero-based positions first. A circle containing one person has survivor index 0. Suppose you already know the survivor index for a circle of size size - 1. Adding one person creates a circle of size size, and the first removal shifts the reference point by k positions. Therefore, the old survivor moves to index (old survivor + k) modulo size. Repeating this from size 2 through n builds the answer without storing the circle.

Josephus survivor indices while growing a circleThe figure shows three small circles labeled with sizes 1, 2, and 3. The size 1 circle marks position 0 as its survivor. Arrows to the larger circles are labeled shift by k, and each destination position wraps around using modulo the new circle size. The picture makes clear that the survivor is carried forward one circle size at a time rather than found by replaying every removal.0*01*012*0 + k ≡ 1 (mod 2)1 + k ≡ 2 (mod 3)Josephus survivor recurrence (k = 1)size 1size 2size 3* = survivor S(n) = (S(n−1) + k) mod n

Approachbuild one zero-based survivor position at a time

  1. Start survivor at 0 for a circle of one person, because the only zero-based index in that circle is 0.
  2. For every circle size from 2 through n, update survivor to (survivor + k) modulo size, because growing the circle shifts the smaller-circle answer by k positions and wrapping keeps it inside the new circle.
  3. Store the addition in a wider integer type, because k can be as large as 2,147,483,647 and survivor + k may exceed the signed int range before modulo is applied.
  4. After the loop, add 1 to survivor, because the computation used zero-based positions while the required labels run from 1 through n.
  5. Return the converted value, rather than the zero-based survivor, because returning survivor directly would be off by one for every input.

Complexitylinear time and constant working memory

MEASUREBOUNDWHY
TimeO(n)The loop performs one constant-time update for each circle size from 2 through n. Each update discards the previous circle representation, so no person is searched for, removed, or shifted repeatedly.
SpaceO(1) extraOnly the current survivor index and loop variable are stored; the returned label is output storage and is excluded. The bound stays constant even for the largest or most uneven removal pattern because no circle or recursion stack is allocated.
Here n is the number of people and k is the counting step.

Annotated solutionC++ · iterative dynamic programming · constant extra space

CPPBuild the zero-based survivor for every circle size, then convert it to a 1-based label.
#include <vector>
using namespace std;

class Solution {
public:
    int josephus(int n, int k) {
        long long survivor = 0;

        for (int size = 2; size <= n; ++size) {
            survivor = (survivor + (long long)k) % size;
        }

        return (int)survivor + 1;
    }
};

The loop invariant is the key line of reasoning: immediately before processing size, survivor is the zero-based survivor for a circle of size - 1. Adding k and taking modulo size transforms that known position into the survivor position for the new circle. The final conversion is deliberately outside the loop, so every recurrence remains in zero-based coordinates.

The recursive alternativethe same recurrence, with stack space instead of a loop

CPPExpress the same zero-based recurrence recursively from the one-person base case.
#include <vector>
using namespace std;

class Solution {
public:
    int josephus(int n, int k) {
        return solve(n, k) + 1;
    }

private:
    long long solve(int size, int k) {
        if (size == 1) return 0;
        return (solve(size - 1, k) + (long long)k) % size;
    }
};

This is a different arrangement, not an optimisation. It mirrors the mathematical recurrence clearly, but it creates one call frame for every circle size, so its extra space is O(n) and a large n can exhaust the runtime stack. The iterative solution keeps the same O(n) time while reducing working space to O(1), which is why it is the safer submission here.

Common mistakesthree wrong code shapes that produce plausible-looking answers

Previous · Sort a Stack