← Wells Fargo questions
CodingEasy

Josephus Problem elimination

Filed under Wells Fargo

Free read 3 of 3

The 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

  1. The Josephus problem follows the recurrence J(n, k) = (J(n-1, k) + k) % n with J(1, k) = 0.

Solution

O(N) time, O(1) space

Python
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.