Josephus Problem

Pattern:

Idea:

Intuition : Intuition behind Josephus Problem

---

💻 Code

Recursive

def josephus(n, k):

    if n == 1:
        return 0

    return (josephus(n - 1, k) + k) % n

Time complexity - O(n) Aux. Space complexity - O(n) , recursion stack

Iterative

def josephus(n, k):

    ans = 0

    for i in range(2, n + 1):
        ans = (ans + k) % i

    return ans

This is 0-index based, as i gives 0 to i-1 values, so for ‘1’ ans is 0. For 1-based indexing, simply return the final ans + 1.

Time - O(n) Aux space - O(1)

---

Problem Statement

There are n people standing in a circle numbered from

0 to n-1

Starting from person 0, every k-th person is eliminated.

The process continues until only one person remains.

Find the safe position (the position of the last surviving person).

Note: This note uses 0-based indexing, which is the convention followed in most DSA books and interviews. For 1-based indexing, simply add 1 to the final answer.

---

Example

Suppose

n = 5

k = 2

People

0 1 2 3 4

Elimination order

1

3

0

4

Remaining

2

Answer

2

---

Key Observation

Suppose we already know the answer for

n - 1

people.

Can we use it to find the answer for

n

people?

Yes.

After the first elimination, the remaining people form the same Josephus problem, just with one fewer person.

The only difference is that their numbering has shifted.

This leads to a simple recurrence.

---

Recurrence Relation

Let

$$J(n,k)$$

denote the safe position.

Base case

$$J(1,k)=0$$

Recursive relation

$$\boxed{J(n,k)=\left(J(n-1,k)+k\right)\bmod n}$$

This is the most important formula for the Josephus problem.

---

Why Does This Formula Work?

Suppose

n = 5

k = 2

The first eliminated person is

(2-1) % 5 = 1

Remaining circle

2 3 4 0

Notice that this is simply another Josephus problem with 4 people.

If the safe position in this smaller problem is

x

we must convert it back to the original numbering.

That conversion is exactly

$$(x+k)\bmod n$$

which gives

$$J(n,k)=\left(J(n-1,k)+k\right)\bmod n$$

---

Recursive Solution

Python Code

def josephus(n, k):

    if n == 1:
        return 0

    return (josephus(n - 1, k) + k) % n

---

Dry Run

Suppose

n = 5

k = 2

Start from the base case.

J(1)

=

0

Now compute upwards.

J(2)

=

(0 + 2) % 2

=

0

J(3)

=

(0 + 2) % 3

=

2

J(4)

=

(2 + 2) % 4

=

0

J(5)

=

(0 + 2) % 5

=

2

Answer

2

---

Iterative Solution (Preferred)

The recurrence depends only on the previous answer.

Therefore, recursion can easily be converted into iteration.

Python Code

def josephus(n, k):

    ans = 0

    for i in range(2, n + 1):
        ans = (ans + k) % i

    return ans

This is generally preferred because it avoids recursion stack overhead.

---

Complexity Analysis

Recursive Solution

• Time Complexity: $O(n)$
• Auxiliary Space Complexity: $O(n)$

(recursion stack)

---

Iterative Solution

• Time Complexity: $O(n)$
• Auxiliary Space Complexity: $O(1)$

---

1-Based Indexing

Some interview problems number people from

1 to n

instead of

0 to n-1

In that case,

simply return

josephus(n, k) + 1

Example

0-based answer

2

becomes

1-based answer

3

---

Common Interview Questions

Q1. What is the recurrence relation?

$$J(n,k)=\left(J(n-1,k)+k\right)\bmod n$$

---

Q2. Why is the answer shifted by k?

After the first elimination,

the remaining people form the same problem,

but the numbering starts from the next person.

The modulo operation maps the shifted numbering back to the original circle.

---

Q3. Which solution should I write?

Unless recursion is specifically requested,

prefer the iterative solution because it uses constant extra space.

---

Q4. Can it be solved faster than $O(n)$?

For a general value of k, the standard solution is $O(n)$.

There are specialized optimizations for certain values (especially k = 2), but they are usually beyond the scope of typical coding interviews.

---

Special Case: k = 2

When every second person is eliminated,

there is a direct mathematical solution.

Let

$$n = 2^m + l$$

where

$$0 \le l < 2^m$$

Then,

$$\boxed{J(n,2)=2l}$$

for 0-based indexing.

For 1-based indexing,

$$\boxed{J(n,2)=2l+1}$$

This formula is occasionally asked in advanced interviews but is not expected unless the interviewer specifically hints at it.

---

Key Takeaways

• The Josephus problem is a classic recursion problem based on reducing the circle size by one after each elimination.
• Recurrence relation:

$$J(1,k)=0$$ $$J(n,k)=\left(J(n-1,k)+k\right)\bmod n$$

• Recursive solution:

def josephus(n, k):

    if n == 1:
        return 0

    return (josephus(n - 1, k) + k) % n

• Iterative solution:

def josephus(n, k):

    ans = 0

    for i in range(2, n + 1):
        ans = (ans + k) % i

    return ans

Method	Time Complexity	Auxiliary Space
Recursive	$O(n)$	$O(n)$
Iterative	$O(n)$	$O(1)$

Interview Tip: The hardest part of the Josephus problem is deriving the recurrence, not writing the code. Once you remember the relation $J(n,k)=(J(n-1,k)+k)\bmod n$, both the recursive and iterative implementations become straightforward.