Josephus Circle using Circular Linked List in C++
By Pranav PrakasanThis article demonstrates the solution to the Josephus Circle Problem using Circular Linked List in C++. There are many methods by which the solution to this problem may be found. Here, we discuss an approach using a circular linked list.
Josephus Circle Problem
The Josephus Circle problem is defined informally as the following.
There are a set of people arranged forming a circle. Each person executes the person next to him/her in a specified direction. i.e. If the first person kills the person to his left, this direction is maintained. The last person to stay alive is freed. It is the position of this person, that we are to find.
In other words, we have to find a safe spot where a person has to stand, to stay alive thereby be freed.
C++ Program: Josephus Circle using Circular Linked List
The Josephus Circle Problem definition gives us a hint to an approach we may take to solve the problem using Circular Linked Lists. Since the next person sitting is executed, which is analogous to removing the next node from the circular list initially formed, this is exactly what we have to do.
We first take the input of the total number of people forming the circle. Then, we create a circular linked list with the elements as numbers from ‘1’ to ‘n’. Now, we delete the nodes that are next to each other, until we are left with just one node. The node number of this node is the position we are looking for.
Now, have a look at the code.
Code
#include<iostream>
using namespace std;
int counter = 1;
struct node
{
int number;
node *next;
};
node *start = NULL, *temp = NULL;
node *create(int num)
{
node *newnode = new node;
newnode -> number = num;
newnode -> next = NULL;
return newnode;
}
void insertNode(int value)
{
if(start == NULL)
{
start = temp = create(value);
}
else
{
temp -> next = create(value);
temp = temp -> next;
}
}
int main()
{
node *delptr = NULL;
int num = 1;
cout<<"ENTER NUMBER : ";
cin>>num;
while(counter<num + 1)
{
insertNode(counter);
counter++;
}
temp -> next = start;
temp = start;
while(true)
{
if(temp -> next -> number == temp -> number)
{
cout<<"REQUIRED POSITION : "<<temp -> number;
break;
}
delptr = temp -> next;
temp -> next = delptr -> next;
delete delptr;
temp = temp -> next;
}
return 0;
}
Output
ENTER NUMBER : 19 REQUIRED POSITION : 7
Analysis
We first create a circular linked list with ‘n’ nodes. Next, we set the temporary pointer as the start pointer and start traversing the circular linked list. We delete the links to the next pointer to the node that is under consideration. We continue this until we are left with just one node in the system.
Hence, at this stage, we have a self-loop, where the last node points to itself. Hence, we may mark this as our exit condition. We exit the loop when the next element has the same value as that of the node under consideration – since we know that all the elements of the list are unique – indicating that we have reached the last remaining node in the system.
Once we exit the loop, we have with us the position where a person has to stand, to stay alive and hence be freed. Hence, we print this value. This is how we can use a Circular Linked List to solve the Josephus Problem.
Feel free to read the following articles.
Leave a Reply