Josephus problem
A hard Recursion interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Recursion
- Sheets
- 1
- Core for
- 11 roles
The problem
Given n people standing in a circle and counting every k-th person until one remains, find the position of the last person.
Example 1
- Input
- n = 5, k = 2
- Output
- 3
- Why
- People are eliminated in order 2, 4, 1, 5, leaving person at position 3.
Example 2
- Input
- n = 6, k = 5
- Output
- 1
- Why
- People are eliminated in order 5, 4, 3, 2, 6, leaving person at position 1.
Constraints
- 1 <= n <= 500
- 1 <= k <= 500
How to think about it
Updated 2026-09-29After the first elimination, the circle shrinks to size n - 1 with the starting pointer shifted. The survivor in the smaller circle has the exact same relative position, so the original survivor index can be reconstructed by shifting the smaller answer forward by k modulo size.
Approaches, worst first
List simulation
time O(n^2) · space O(n)
Populate a list of numbers 1 to n and simulate circular stepping and removal. Each deletion shifts remaining elements in linear time, degrading total performance.
Recursive Josephus recurrence
time O(n) · space O(n)
Use f(n, k) = (f(n - 1, k) + k) % n with base case f(1, k) = 0. Directly maps the survivor index from subproblem to problem in O(n) calls.
Bottom-up iterative transitionWrite this one
time O(n) · space O(1)
Compute the recurrence iteratively starting from a survivor index of 0 at size 1 up to size n. Avoids function call recursion overhead completely and requires only one scalar variable.
Where people lose marks · 2
- 1-based versus 0-based indexing mismatch. The modulo formula (ans + k) % i works strictly on 0-based indices; forgetting to add 1 at the end returns an off-by-one result.
- Stepping by k without modulo during list simulation, causing index out of bounds when k exceeds remaining size.
The theory behind it
Recursion — the ground this problem stands on. All Recursion problems
What Recursion is
Recursion is a nesting doll that opens to reveal an identical smaller doll inside. In programming, a function solves a substantial problem by delegating smaller versions of the exact same question to fresh invocations of itself. Each invocation operates on shrunken input until hitting an irreducible foundation called a base case, which returns an immediate answer and permits the waiting cascade to resolve backwards.
When to reach for it
Reach for recursion when a problem possesses self-similar subproblems, such as traversing branched tree structures, exploring graph pathways, or generating combinations. Phrases asking for all permutations, subset generation, exhaustive maze navigation, or hierarchical file system traversals signal recursive decomposition. It is natural whenever the answer to a large instance depends on assembling identical solutions for smaller subsets.
How the pattern works
Structure every recursive method around two mandatory stages: the termination stop and the shrinking recurrence. Write the base condition first so the function exits before attempting further execution. Next, trust the recursive call to return valid answers for smaller inputs without mentally unwinding every level at once. Pass accumulation state forward through parameters, or combine child return values on the ascent phase once deeper calls return.
More Recursion problems
Target Roles
Core requirement for 11 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .