Josephus Problem in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int josephus(int n,int k){return n==1?0:(josephus(n-1,k)+k)%n;}
int main(){
    int n=7,k=3;
    printf("Safe Position: %d\n", josephus(n,k)+1);
}

C Output

Input:  
n = 7, k = 3 (7 people, every 3rd is eliminated

Output:  
Safe Position: 4

C++ Program

#include <bits/stdc++.h>
using namespace std;
int josephus(int n,int k){return n==1?0:(josephus(n-1,k)+k)%n;}
int main(){
    int n=5,k=2;
    cout<<"Safe Position: "<<josephus(n,k)+1;
}

C++ Output

Input:  
n = 5, k = 

Output:  
Safe Position: 3

JAVA Program

class Main{
    static int josephus(int n,int k){
        return n==1?0:(josephus(n-1,k)+k)%n;
    }
    public static void main(String[] args){
        int n=6,k=5;
        System.out.println("Safe Position: "+(josephus(n,k)+1));
    }
}

JAVA Output

Input:  
n = 6, k = 5 

Output:  
Safe Position: 1

Python Program

def josephus(n,k):
    return 0 if n==1 else (josephus(n-1,k)+k)%n
n,k=8,4
print("Safe Position:", josephus(n,k)+1)

Python Output

Input:  
n = 8, k = 4
Output:  
Safe Position: 1

Detailed Explanation

Problem Statement

Suppose there are n individuals in a circle. You count off in the circle and kill every k-th individual until one is left. The problem is: Where should you stand to live?

Step-by-Step Example (C example: n = 7, k = 3)

Individuals are numbered from 1 to 7.

Begin at 1, count: 1 (count 1), 2 (count 2), 3 (count 3) → remove person 3. Remaining: 1, 2, 4, 5, 6, 7.

Keep counting from 4: 4 (count 1), 5 (count 2), 6 (count 3) → remove person 6. Remaining: 1, 2, 4, 5, 7.

Pick up from 7: 7 (count 1), 1 (count 2), 2 (count 3) → remove person 2. Remaining: 1, 4, 5, 7.

Continue from 4: 4 (count 1), 5 (count 2), 7 (count 3) → remove person 7. Left with: 1, 4, 5.

Continue from 1: 1 (count 1), 4 (count 2), 5 (count 3) → remove person 5. Left with: 1, 4.

Continue from 1: 1 (count 1), 4 (count 2), back to 1 (count 3) → remove person 1. Left with: 4.

Survivor = position 4.

Mathematical Recurrence

If we number positions from 0 to n-1, the recurrence relation is:

J(1, k) = 0  // Base case: just one person remains alive at index 0

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

Then we append 1 at the end to translate from 0-based indexing to 1-based.

Why Recursion Works

When any one person is eliminated, the circle "narrows" but the numbering changes. The recurrence compensates for this change by adding k to the last safe position and doing modulo with the number of people present now.

Complexity

Time: O(n) since we're making one recursive call for every person.

Space: O(n) for recursion stack (can be optimized to O(1) using an iterative solution).

Real-Life Applications

Selecting leaders or winners in circular games (Hot Potato).

Military tactics (Josephus narrative originally about survival during siege).

Computer networks — token passing ring topology can employ Josephus logic.

Load balancing in distributed systems.

Common Pitfalls

Forgetting the +1 for 1-based positions.

Confusing k as zero-indexed rather than count-based.

Not realizing once a person is eliminated, the problem doesn't change for smaller circles.