Josephus Problem: Find the Survivor Using Recursion and Modular Arithmetic
Problem Statement
There are n people standing in a circle numbered from 1 to n.
Starting from person 1, every k-th person is eliminated.
After each elimination, counting continues from the next surviving person.
The process repeats until only one person remains.
Your task is to find the position of the survivor.
Example
Input
n = 5
k = 2
Elimination Process
1 2 3 4 5
^
Kill 2
1 3 4 5
^
Kill 4
1 3 5
^
Kill 1
3 5
^
Kill 5
Remaining Person
3
Output
3
Why Brute Force Is Not Ideal
A straightforward approach would be:
Store all people in a circular structure.
Keep counting around the circle.
Remove every k-th person.
Although intuitive, this approach involves repeated deletions and circular traversal.
The beauty of the Josephus Problem lies in a mathematical recurrence that completely avoids simulation.
The Key Insight
Instead of focusing on eliminations, think about what happens after the first person is removed.
Suppose we have:
n people
After one elimination:
n - 1 people remain
The remaining people still form a smaller Josephus problem.
This observation allows us to build the answer recursively.
Understanding the Recurrence
Let's first work with 0-based indexing.
Define:
J(n, k)
as the survivor's position among n people.
Base Case
If there is only one person:
J(1, k) = 0
because the only person survives.
Recursive Relation
Suppose we already know:
J(n - 1, k)
which represents the survivor among n - 1 people.
When we add the eliminated position back into the circle, all positions shift.
The survivor's new position becomes:
J(n,k)=(J(n-1,k)+k)\bmod n
This is the famous Josephus recurrence.
Visual Intuition
Consider:
n = 5
k = 2
After the first elimination:
1 3 4 5
The circle has effectively rotated.
The survivor position found in the smaller problem must be shifted by k positions to map back to the original circle.
That shift is exactly:
(+ k) % n
which gives:
J(n,k)=(J(n-1,k)+k)\bmod n
Dry Run
Let:
n = 5
k = 2
Step 1
J(1) = 0
Step 2
J(2) = (0 + 2) % 2
= 0
Step 3
J(3) = (0 + 2) % 3
= 2
Step 4
J(4) = (2 + 2) % 4
= 0
Step 5
J(5) = (0 + 2) % 5
= 2
Result in 0-Based Indexing
2
Convert to 1-Based Indexing
2 + 1 = 3
Final Answer
3
Recursive Solution
class Solution {
public:
int josephus(int n, int k) {
if(n == 1)
return 1;
return (josephus(n - 1, k) + k - 1) % n + 1;
}
};
Why Does the Formula Use k - 1?
The recurrence:
J(n,k)=(J(n-1,k)+k)\bmod n
is derived using 0-based indexing.
However, the problem uses 1-based indexing.
To keep all calculations in 1-based form, we use:
(josephus(n - 1, k) + k - 1) % n + 1
This adjustment ensures the result remains valid in 1-based indexing throughout the recursion.
Iterative Solution
The same recurrence can be computed iteratively.
class Solution {
public:
int josephus(int n, int k) {
int ans = 0;
for(int i = 2; i <= n; i++) {
ans = (ans + k) % i;
}
return ans + 1;
}
};
Why the Iterative Version Is Better
The recursive solution creates a recursion stack of depth:
n
The iterative solution computes the same recurrence without recursion.
Benefits
Complexity Analysis
Recursive Solution
Time Complexity
O(n)
Space Complexity
O(n)
due to the recursion stack.
Iterative Solution
Time Complexity
O(n)
Space Complexity
O(1)
Mathematical Pattern
The Josephus Problem is one of the most famous recurrence-based problems.
It teaches important concepts such as:
The core transformation is:
Large Problem
↓
Smaller Circle
↓
Shift Survivor Position
↓
Original Answer
Interview Takeaway
Whenever a problem involves:
Circular elimination.
Repeated removals.
Survivor position.
Rotation after deletion.
Think about:
Recursive Reduction + Modular Arithmetic
The Josephus recurrence:
J(n,k)=(J(n-1,k)+k)\bmod n
is one of the most important formulas in competitive programming and technical interviews.
Key Formula to Remember
For 0-Based Indexing
J(1,k)=0
and
J(n,k)=(J(n-1,k)+k)\bmod n
For 1-Based Indexing
Answer = J(n, k) + 1
This computes the survivor in linear time without simulating eliminations.
Key Takeaway
The crucial insight is that after each elimination, the remaining people form a smaller Josephus problem. By solving the smaller problem and shifting the survivor's position using modular arithmetic, we obtain an elegant recurrence that avoids expensive simulation. This transforms a seemingly complex circular elimination process into a simple O(n) solution.
Summary
The Josephus Problem asks us to determine the last surviving person in a circle after repeatedly eliminating every k-th person. Instead of simulating the eliminations, we use a mathematical recurrence based on modular arithmetic. The recurrence relation allows us to build the answer from smaller subproblems, resulting in an efficient O(n) solution. The iterative version is generally preferred because it achieves the same result with constant extra space.