Last Updated: Mar 27, 2024
Difficulty: Medium

# Josephus Circle Implementation Using STL List

## Introduction

Have You ever heard about the “Game of Death in a Circle” Puzzle? Have you ever tried to solve that Deadly Puzzle? This is an exciting problem commonly known as the Josephus Circle problem. Do you know how to implement this?

Don’t worry if you don’t know, as we will discuss the Implementation of the Josephus Circle problem using STL lists. At first, we will discuss the problem and its solution in detail then we will move to the Implementation part of the solution. So, without further ado, let’s start.

### Problem Statement

People are gathered in a circle, awaiting execution. Counting begins at a specific point on the circle and moves in one particular direction around it. The following person is executed when a certain number of individuals have been skipped. The practice is repeated with the remaining persons, beginning with the next person, proceeding in the same direction, and skipping the same amount of individuals until only one person is left, who is then released.

The task is to find a place in the initial circle to escape execution, given the number of personsstarting pointdirection, and number to be skipped.

This puzzle's "regular" variation involves skipping one person at a time. For the time being, let's concentrate on this.

### Example

Here is an example of the Josephus Circle Implementation Problem.

With 13 persons in the circle, here's a visual representation of how the puzzle functions:

The following is the order of deaths: 2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3; position 11 is the winner.

In general, how can we readily select the winner? Let's get started with the problem discussed in detail.

### Explanation

Let's break the problem into smaller ones to see the solution to the Josephus Circle Implementation problem. We will find a general formula for the winner of this deadly circle.

When we have five persons:

The winner, in this case, is the person at position 3.

When we have six persons:

The winner, in this case, is the person at position 5.

When we have seven persons:

The winner, in this case, is the person at position 5.

• The first important thing: All winning positions must be Odd numbers. So, the even numbers get eliminated first.
• The second thing: they appear to continue increasing by two each time until they reset to 1.

Here's a list of winning positions we'll be able to obtain by working out different numbers of persons in the Josephus Circle Implementation Problem:

When the no of persons is a power of 2, the person in the first position will survive.

The person at 1 is only eliminated if the total number of persons in the circle is odd at any point during its turn. This implies that the last person would not be killed and instead kill the person at 1.

Here comes our formula: In terms of m, for the position. The position of the last person standing is 2m+1 for n = 2k + m (with the maximum possible number k, providing that m is nonnegative).

Let us now apply this to Josephus himself.

Because 40 other soldiers accompanied Josephus, his n value was 41. This produces a value of 32 for 2k and 9 for m. In order to be rescued, Josephus must sit in position 2m+1 = 2(9)+1 = 19.

## Approach

We are using the list container based on the idea of a circular list for our solution.

### Algorithm

Let’s begin with the algorithm of the Josephus Circle Implementation Problem.

• We'll create a circular linked list of size n, with each node's data being the list's position number.
• Then we'll traverse the list, deleting the mth node each time until there's just one node remaining.
• Finally, the left node is our solution to the problem.

### Implementation in C++

The given code is the Josephus circle implementation in the C++ language using STL lists.

Code

``````#include <bits/stdc++.h>
using namespace std;
int JosephusCirclePuzzle(int n, int m)
// n is length of the circle, m is count to choose next person
{
list<int> lst; //using STL container to create a double linked list
for (int i = 0; i < n; i++)
{
lst.push_back(i);
}
//declaring iterator for traversing list
auto count = lst.begin();

while (lst.size() > 1)
{
for (int i = 1; i < m; i++)
{
count++;
if (count == lst.end())
{
count = lst.begin();
}
}
count = lst.erase(count);
if (count == lst.end())
{
count = lst.begin();
}
}
return lst.front(); // returns the first element of the list
}
//driver  code
int main()
{
int n, m;
cout << "enter the values of n and m:\n";
cin >> n >> m;
cout << "The last person remaining at position " << JosephusCirclePuzzle(n, m);
}``````

Output

#### Complexity Analysis

Time Complexity: The time complexity of our solution is O(n*m) as we are using a nested loop.

Auxiliary Space: The auxiliary space required for our solution using STL lists is O(n).

### Implementation in Python

The given code is the Josephus circle implementation problem in Python language.

Code

``````class Node:
def __init__(self, x):
self.data = x
self.next = None
def JosephusCirclePuzzle(n, m):

for i in range(2, m + 1):
prev.next = Node(I)
prev = prev.next
prev.next = head # Connecting last node to first node

# looping till only one node is left
while (ptr1.next != ptr1):

# Finding nth node
count = 1
while (count != n):
ptr2 = ptr1
ptr1 = ptr1.next
count += 1

#  Removing the n-th node
ptr2.next = ptr1.next
ptr1 = ptr2.next

print("The Last person remaining at position, "ptr1.data)

#  Driver code
if __name__ == '__main__':
m = 8
n = 2
print("The Size of the circle is ",m)
print("The count of the person to choose next is ",n)
JosephusCirclePuzzle(n, m)``````

Output

#### Complexity Analysis

Time Complexity: The time complexity of our solution is O(n*m) as we are using a nested loop.

Auxiliary Space: The auxiliary space required for our solution is O(n).

Also see, Rabin Karp Algorithm.

### What is the time complexity of the Josephus Circle Implementation using STL Lists?

The time complexity of the implementation of Josephus Circle using STL lists is O(n*m). Where n is the size of the circle and m is the count to choose the next person.

### Can we solve the Josephus Circle Implementation problem using recursion?

Yes, recursion can be used to solve the Josephus problem. Recursively eliminate the mth position for each iteration until just one person remains.

### What is the significance of STL?

The Standard Template Library (STL) is a collection of C++ template classes for famous programming data structures and functions like listsstacks, and arrays. It's a container library with algorithms, iterators, and container classes. It is a parameterized library since it is a generic library.

## Conclusion

This blog discussed the deadly puzzle of Josephus. We discussed the Josephus Circle Implementation Problem using the STL lists.

We have discussed:

• Problem statement of Josephus circle implementation.
• Example of the given Josephus circle implementation problem.
• Explanation of the solutions of the Josephus circle implementation.
• Algorithm for the solution using the linked lists method.
• Implementation of the Algorithm.

You can learn more about STL, such as STL in C++, Algorithms in C++ STLContainers in STL, and many more STL lists.

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations, and much more!!

We wish you Good Luck! Keep coding and keep reading Ninja!!

Topics covered
1.
Introduction
1.1.
Problem Statement
1.2.
Example
1.3.
Explanation
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
2.3.
Implementation in Python
2.3.1.
Complexity Analysis
3.