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 persons, starting point, direction, 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.
Also read - Merge sort in linked list
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):
head = Node(1)
prev = head
for i in range(2, m + 1):
prev.next = Node(I)
prev = prev.next
prev.next = head # Connecting last node to first node
ptr1 = head
ptr2 = head
# 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.