# What Is Josephus Problem in Data Structure?

//

Angela Bailey

The Josephus problem is a well-known problem in the field of data structures and algorithms. It is named after the Jewish historian Flavius Josephus, who first described the problem in the first century AD. The problem is defined as follows:

## Problem Statement

A group of n people are standing in a circle. Starting from a given person, we count k people in the circle in a clockwise direction and eliminate that person. We continue this process, starting from the next person in the circle, until only one person remains.

### Example

Let’s understand the problem with an example. Consider a circle of 7 people numbered from 1 to 7.

• Step 2: Count 3 people clockwise (including the starting person) and eliminate person number 3.
• Step 3: Start from the next remaining person, which is number 4.
• Step 4: Count 3 people clockwise (including the starting person) and eliminate person number 6.
• Step 5: Start from the next remaining person, which is number 7.
• Step 6: Count 3 people clockwise (including the starting person) and eliminate person number 2.

This process continues until only one person remains. In this example, after eliminating persons numbered as mentioned above, we are left with only one person: number 5.

## Solution Approach

The Josephus problem can be solved using various approaches. One of the most common approaches is to use a circular linked list. In this approach, we create a circular linked list with n nodes, each representing a person in the circle.

We then start from the first person and iterate through the circle, eliminating every k-th person. After eliminating a person, we move to the next person in the circle and repeat the process until only one person remains.

### Code Example

Here is an example implementation of the Josephus problem using a circular linked list:

``````
class Node {
int data;
Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

public class JosephusProblem {

public static int josephus(int n, int k) {
// Create a circular linked list

for (int i = 2; i <= n; i++) {
prev.next = new Node(i);
prev = prev.next;
}

// Connect last node to first node to make it circular

// Iterate through the circle and eliminate every k-th person
for (int i = 1; i < k - 1; i++) {
}

// Eliminate the k-th person

// Move to the next person
}

return head.data; // Return the last remaining person's number
}

public static void main(String[] args) {
int n = 7; // Number of people in the circle
int k = 3; // Count k people in a clockwise direction

int lastPerson = josephus(n, k);
System.out.println("The last remaining person is " + lastPerson);
}
}
```
```

By running the above code, you will get the output:

````The last remaining person is 5`
```

## Conclusion

The Josephus problem is an interesting problem in data structures and algorithms. It involves eliminating people standing in a circle until only one person remains. In this article, we discussed the problem statement, its solution approach using a circular linked list, and provided a code example in Java.

Understanding and solving such problems can help improve your problem-solving skills and deepen your understanding of data structures and algorithms.