Josephus Problem – Understanding the Famous Recurrence

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

Output

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

Convert to 1-Based Indexing

2 + 1 = 3

Final Answer

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:

The iterative solution computes the same recurrence without recursion.

Benefits

No recursion stack overhead.
Better memory usage.
Easier debugging.
Safer for large values of n.

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:

Circular indexing.
Modular arithmetic.
Recursive state reduction.
Position shifting after deletion.

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.