Josephus Problem — Editorial

Opening the reading…

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.

Approachbuild one zero-based survivor position at a time

Start survivor at 0 for a circle of one person, because the only zero-based index in that circle is 0.

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.

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.

After the loop, add 1 to survivor, because the computation used zero-based positions while the required labels run from 1 through n.

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

MEASURE	BOUND	WHY
Time	O(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.
Space	O(1) extra	Only 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.