Introduction

The Josephus Problem involves eliminating people in circular order.

Given:

  • n people standing in a circle
  • every k-th person is eliminated

The task is to:

  • find the last surviving person

This problem is one of the most important applications of:

 Queue Simulation + Circular Traversal

This problem helps in understanding:

  • circular queues
  • recursion
  • elimination logic
  • mathematical recurrence relations

Example

Input:n = 5
k = 2

Output:
3

Explanation:
People:
1 2 3 4 5

Elimination Order:
2 → 4 → 1 → 5

Remaining person:
3

Constraints

1 <= n <= 5001 <= k <= 500

Approach 1 : Queue Simulation

Explanation

The simplest way is:

  1. Place all people in queue
  2. Rotate queue k-1 times
  3. Remove k-th person
  4. Repeat until one person remains

This directly simulates elimination.

Steps

  1. Insert all people into queue.
  2. Rotate first k-1 people.
  3. Remove front person.
  4. Continue until one remains.
  5. Return survivor.

Dry Run

Input:n = 5
k = 2

Queue:
1 2 3 4 5

Rotate:
1 moves back

Remove:
2

Queue:
3 4 5 1

Continue process...

Remaining:
3

Queue Simulation Code

Complexity Analysis

Time Complexity: O(n * k)
Explanation:
Queue rotations occur repeatedly.

Space Complexity: O(n)
Explanation:
Queue stores all people.

Approach 2 : Mathematical Recursion

Explanation

The optimized solution uses:

 Josephus Recurrence Relation

The recurrence formula is:

 f(n,k) = (f(n-1,k) + k) % n

Base Case:

 f(1,k) = 0

Final answer:

  • add 1
    for 1-based indexing

This avoids full simulation.

Steps

  1. Define recursive formula.
  2. Solve smaller subproblem.
  3. Shift survivor position.
  4. Return final answer.

Dry Run

n = 1Survivor = 0

n = 2
(0 + 2) % 2 = 0

n = 3
(0 + 2) % 3 = 2

n = 4
(2 + 2) % 4 = 0

n = 5
(0 + 2) % 5 = 2

Final Answer:
2 + 1 = 3

Mathematical Recursion Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Recurrence is solved once for every person.

Space Complexity: O(n)
Explanation:
Recursive stack space is used.

Edge Cases

  1. n = 1
  2. k = 1
  3. Large k value
  4. Large n value
  5. Circular elimination wraparound

Why This Problem is Important

Josephus Problem helps in understanding:

  1. Circular queue traversal
  2. Recursive recurrence relations
  3. Elimination simulation
  4. Mathematical optimization
  5. Queue rotation logic

It is one of the most important recursion and queue interview problems.

Real-World Applications

Josephus concepts are used in:

  1. Circular scheduling systems
  2. Multiplayer elimination games
  3. Distributed systems
  4. Load balancing rotation
  5. Process elimination simulations

Common Mistakes

  1. Incorrect indexing
  2. Forgetting modulo operation
  3. Wrong base case
  4. Incorrect queue rotation

Interview Tips

Interviewers often expect:

  1. Queue simulation explanation
  2. Recursive recurrence reasoning
  3. Circular traversal understanding

Always explain:

  • why modulo handles circular movement
  • how recurrence shifts survivor position
  • why indexing conversion is needed

Related Questions

  1. Task Scheduler
  2. Interleaving Queue
  3. Circular Queue
  4. Queue Reconstruction
  5. Hot Potato Problem

Final Takeaway

The Josephus Problem is a fundamental circular traversal problem that teaches queue simulation and recursive mathematical optimization techniques. Understanding this problem builds a strong foundation for advanced recursion and circular data structure interview problems.