CodingEasy
Josephus Problem elimination
Filed under Wells Fargo
Free read 3 of 3The Josephus problem follows the recurrence J(n, k) = (J(n-1, k) + k) % n with J(1, k) = 0.
The question
Given N people in a circle and an integer K, eliminate every K-th person until only one remains. Return the position of the survivor.
Constraints
- 1 <= N <= 10^5
- 1 <= K <= N
- Positions are 0-indexed
Examples
- Input
- N=5, K=2
- Output
- 2
- Why
- Sequence of elimination: 1, 3, 0, 4. Survivor is 2.
Approach
The Josephus problem follows the recurrence J(n, k) = (J(n-1, k) + k) % n with J(1, k) = 0.
Use an iterative approach to calculate the survivor position to avoid recursion depth limits.
This approach runs in O(N) time and O(1) space.
Solution
O(N) time, O(1) space
def josephus(n, k):
res = 0
for i in range(2, n + 1):
res = (res + k) % i
return res
Tips
- What they are testing: Tests recursion depth for large N and base cases like K=1.
- Common mistake: Simulating the circle with a list/array, which leads to O(N^2) complexity due to deletions.
Related Wells Fargo questions
Collected from public candidate posts and coding forums. Updated Nov 2026.