Josephus circle using circular linked list
The Josephus problem is a famous theoretical problem related to a certain elimination game. The problem involves a circle of people, and in each step, every nth person is eliminated until only one person remains. This problem can be efficiently solved using a circular linked list data structure.
Problem Statement
Given the number of people in the circle (size) and the value of n (every nth person is eliminated), the task is to determine the position of the last person remaining in the Josephus circle.
Example
For example, consider a Josephus circle with 10 people (size = 10) and n = 4. The people are numbered from 1 to 10. Starting from person 1, every 4th person will be eliminated until only one person remains. After the eliminations, the last remaining person's position will be 5.
Idea to Solve the Problem
To solve the Josephus problem, you can use a circular linked list. Here's the general approach:
- Create a circular linked list with the given number of people.
- Iterate through the linked list and eliminate every nth person until only one person remains.
Pseudocode
function josephusCircle(size, n):
if n <= 0:
return
if n == 1:
// Base case: Only one person remains
print("Josephus Position", size)
return
cll = newCLL()
for i in range(1, size + 1):
addNode(cll, i)
auxiliary = cll.head
back = cll.head
counter = 0
while auxiliary->next != auxiliary:
counter = 1
while counter != n:
back = auxiliary
auxiliary = auxiliary->next
counter++
back->next = auxiliary->next
free(auxiliary)
auxiliary = back->next
print("Josephus Position", auxiliary->data)
Algorithm Explanation
- Create a new circular linked list.
- Iterate through the linked list until only one person remains. In each step:
- Find the nth person to be eliminated.
- Remove that person from the linked list.
- Update the pointers accordingly.
Code Solution
/*
C Program
Josephus circle using circular linked list
*/
#include <stdio.h>
#include <stdlib.h>
// Linked List Node
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Circular List
struct CircularList
{
struct LinkNode *head;
struct LinkNode *rear;
};
// Returns a new linked list
struct CircularList *newCLL()
{
// Create dynamic node
struct CircularList *cll = (struct CircularList *) malloc(sizeof(struct CircularList));
if (cll != NULL)
{
cll->head = NULL;
cll->rear = NULL;
}
else
{
// When memory are not allocated
printf("Memory Overflow to Create Circular List\n");
}
return cll;
}
// Returns a new Node of linked list
struct LinkNode *createLinkNode(int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
// Add node in circular linked list
void addNode(struct CircularList *cll, int data)
{
struct LinkNode *node = createLinkNode(data);
if (cll->head == NULL)
{
// First node of linked list
cll->head = node;
}
else
{
// Add new node at last position
cll->rear->next = node;
}
// Connect the first node to the last
node->next = cll->head;
// Get new last node
cll->rear = node;
}
// Implement josephus circle in circular linked list
void josephusCircle(int size, int n)
{
if (n <= 0)
{
return;
}
if (n == 1)
{
// Base case
printf(" Josephus Position %d \n", size);
return;
}
struct CircularList *cll = newCLL();
// Construct linked list
for (int i = 1; i <= size; ++i)
{
addNode(cll, i);
}
// Define some auxiliary variables
struct LinkNode *auxiliary = cll->head;
struct LinkNode *back = cll->head;
int counter = 0;
// Execute loop until when more than one node in linked list
while (auxiliary->next != auxiliary)
{
// Used to find n-th node
counter = 1;
while (counter != n)
{
// Get current node
back = auxiliary;
// Visit to next node
auxiliary = auxiliary->next;
counter++;
}
// Segregating n-th position node
back->next = auxiliary->next;
// Free the node memory
free(auxiliary);
// Visit to next node
auxiliary = back->next;
}
printf("\n Size : %d N : %d \n", size, n);
// Display last remaining node
printf(" Josephus Position %d \n", auxiliary->data);
}
int main(int argc, char
const *argv[])
{
// Number of element in circle
int size = 10;
int n = 4;
josephusCircle(size, n);
n = 6;
josephusCircle(size, n);
return 0;
}
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
/*
Java Program
Josephus circle using circular linked list
*/
// Linked list Node
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
// Set node value
this.data = data;
this.next = null;
}
}
// Define Circular List
class CircularList
{
public LinkNode head;
public LinkNode rear;
public CircularList()
{
this.head = null;
this.rear = null;
}
// Add node in circular linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
// First node of linked list
this.head = node;
}
else
{
// Add new node at last position
this.rear.next = node;
}
// Connect the first node to the last
node.next = this.head;
// Get new last node
this.rear = node;
}
}
public class JosephusCircle
{
// Implement josephus circle in circular linked list
public void josephusPosition(int size, int n)
{
if (n <= 0)
{
return;
}
if (n == 1)
{
// Base case
System.out.print(" Josephus Position " + size + " \n");
return;
}
CircularList cll = new CircularList();
// Construct linked list
for (int i = 1; i <= size; ++i)
{
cll.addNode(i);
}
// Define some auxiliary variables
LinkNode auxiliary = cll.head;
LinkNode back = cll.head;
int counter = 0;
cll.head = null;
cll.rear = null;
// Execute loop until when more than one node in linked list
while (auxiliary.next != auxiliary)
{
// Used to find n-th node
counter = 1;
while (counter != n)
{
// Get current node
back = auxiliary;
// Visit to next node
auxiliary = auxiliary.next;
counter++;
}
// Segregating n-th position node
back.next = auxiliary.next;
// Visit to next node
auxiliary = back.next;
}
System.out.print("\n Size : " + size + " N : " + n + " \n");
// Display last remaining node
System.out.print(" Josephus Position " + auxiliary.data + " \n");
cll.head = auxiliary;
cll.rear = auxiliary;
}
public static void main(String[] args)
{
JosephusCircle task = new JosephusCircle();
// Number of element in circle
int size = 10;
int n = 4;
task.josephusPosition(size, n);
n = 6;
task.josephusPosition(size, n);
}
}
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Josephus circle using circular linked list
*/
// Linked list Node
class LinkNode
{
public: int data;
LinkNode *next;
LinkNode(int data)
{
// Set node value
this->data = data;
this->next = NULL;
}
};
// Define Circular List
class CircularList
{
public: LinkNode *head;
LinkNode *rear;
CircularList()
{
this->head = NULL;
this->rear = NULL;
}
// Add node in circular linked list
void addNode(int data)
{
LinkNode *node = new LinkNode(data);
if (this->head == NULL)
{
// First node of linked list
this->head = node;
}
else
{
// Add new node at last position
this->rear->next = node;
}
// Connect the first node to the last
node->next = this->head;
// Get new last node
this->rear = node;
}
};
class JosephusCircle
{
public:
// Implement josephus circle in circular linked list
void josephusPosition(int size, int n)
{
if (n <= 0)
{
return;
}
if (n == 1)
{
// Base case
cout << " Josephus Position " << size << " \n";
return;
}
CircularList cll = CircularList();
// Construct linked list
for (int i = 1; i <= size; ++i)
{
cll.addNode(i);
}
// Define some auxiliary variables
LinkNode *auxiliary = cll.head;
LinkNode *back = cll.head;
int counter = 0;
cll.head = NULL;
cll.rear = NULL;
// Execute loop until when more than one node in linked list
while (auxiliary->next != auxiliary)
{
// Used to find n-th node
counter = 1;
while (counter != n)
{
// Get current node
back = auxiliary;
// Visit to next node
auxiliary = auxiliary->next;
counter++;
}
// Segregating n-th position node
back->next = auxiliary->next;
delete auxiliary;
// Visit to next node
auxiliary = back->next;
}
cout << "\n Size : " << size << " N : " << n << " \n";
// Display last remaining node
cout << " Josephus Position " << auxiliary->data << " \n";
cll.head = auxiliary;
cll.rear = auxiliary;
}
};
int main()
{
JosephusCircle task = JosephusCircle();
// Number of element in circle
int size = 10;
int n = 4;
task.josephusPosition(size, n);
n = 6;
task.josephusPosition(size, n);
return 0;
}
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
// Include namespace system
using System;
/*
C# Program
Josephus circle using circular linked list
*/
// Linked list Node
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
// Set node value
this.data = data;
this.next = null;
}
}
// Define Circular List
public class CircularList
{
public LinkNode head;
public LinkNode rear;
public CircularList()
{
this.head = null;
this.rear = null;
}
// Add node in circular linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
// First node of linked list
this.head = node;
}
else
{
// Add new node at last position
this.rear.next = node;
}
// Connect the first node to the last
node.next = this.head;
// Get new last node
this.rear = node;
}
}
public class JosephusCircle
{
// Implement josephus circle in circular linked list
public void josephusPosition(int size, int n)
{
if (n <= 0)
{
return;
}
if (n == 1)
{
// Base case
Console.Write(" Josephus Position " + size + " \n");
return;
}
CircularList cll = new CircularList();
// Construct linked list
for (int i = 1; i <= size; ++i)
{
cll.addNode(i);
}
// Define some auxiliary variables
LinkNode auxiliary = cll.head;
LinkNode back = cll.head;
int counter = 0;
cll.head = null;
cll.rear = null;
// Execute loop until when more than one node in linked list
while (auxiliary.next != auxiliary)
{
// Used to find n-th node
counter = 1;
while (counter != n)
{
// Get current node
back = auxiliary;
// Visit to next node
auxiliary = auxiliary.next;
counter++;
}
// Segregating n-th position node
back.next = auxiliary.next;
// Visit to next node
auxiliary = back.next;
}
Console.Write("\n Size : " + size + " N : " + n + " \n");
// Display last remaining node
Console.Write(" Josephus Position " + auxiliary.data + " \n");
cll.head = auxiliary;
cll.rear = auxiliary;
}
public static void Main(String[] args)
{
JosephusCircle task = new JosephusCircle();
// Number of element in circle
int size = 10;
int n = 4;
task.josephusPosition(size, n);
n = 6;
task.josephusPosition(size, n);
}
}
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
<?php
/*
Php Program
Josephus circle using circular linked list
*/
// Linked list Node
class LinkNode
{
public $data;
public $next;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->next = null;
}
}
// Define Circular List
class CircularList
{
public $head;
public $rear;
function __construct()
{
$this->head = null;
$this->rear = null;
}
// Add node in circular linked list
public function addNode($data)
{
$node = new LinkNode($data);
if ($this->head == null)
{
// First node of linked list
$this->head = $node;
}
else
{
// Add new node at last position
$this->rear->next = $node;
}
// Connect the first node to the last
$node->next = $this->head;
// Get new last node
$this->rear = $node;
}
}
class JosephusCircle
{
// Implement josephus circle in circular linked list
public function josephusPosition($size, $n)
{
if ($n <= 0)
{
return;
}
if ($n == 1)
{
// Base case
echo " Josephus Position ". $size ." \n";
return;
}
$cll = new CircularList();
// Construct linked list
for ($i = 1; $i <= $size; ++$i)
{
$cll->addNode($i);
}
// Define some auxiliary variables
$auxiliary = $cll->head;
$back = $cll->head;
$counter = 0;
$cll->head = null;
$cll->rear = null;
// Execute loop until when more than one node in linked list
while ($auxiliary->next != $auxiliary)
{
// Used to find n-th node
$counter = 1;
while ($counter != $n)
{
// Get current node
$back = $auxiliary;
// Visit to next node
$auxiliary = $auxiliary->next;
$counter++;
}
// Segregating n-th position node
$back->next = $auxiliary->next;
// Visit to next node
$auxiliary = $back->next;
}
echo "\n Size : ". $size ." N : ". $n ." \n";
// Display last remaining node
echo " Josephus Position ". $auxiliary->data ." \n";
$cll->head = $auxiliary;
$cll->rear = $auxiliary;
}
}
function main()
{
$task = new JosephusCircle();
// Number of element in circle
$size = 10;
$n = 4;
$task->josephusPosition($size, $n);
$n = 6;
$task->josephusPosition($size, $n);
}
main();
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
/*
Node Js Program
Josephus circle using circular linked list
*/
// Linked list Node
class LinkNode
{
constructor(data)
{
// Set node value
this.data = data;
this.next = null;
}
}
// Define Circular List
class CircularList
{
constructor()
{
this.head = null;
this.rear = null;
}
// Add node in circular linked list
addNode(data)
{
var node = new LinkNode(data);
if (this.head == null)
{
// First node of linked list
this.head = node;
}
else
{
// Add new node at last position
this.rear.next = node;
}
// Connect the first node to the last
node.next = this.head;
// Get new last node
this.rear = node;
}
}
class JosephusCircle
{
// Implement josephus circle in circular linked list
josephusPosition(size, n)
{
if (n <= 0)
{
return;
}
if (n == 1)
{
// Base case
process.stdout.write(" Josephus Position " + size + " \n");
return;
}
var cll = new CircularList();
// Construct linked list
for (var i = 1; i <= size; ++i)
{
cll.addNode(i);
}
// Define some auxiliary variables
var auxiliary = cll.head;
var back = cll.head;
var counter = 0;
cll.head = null;
cll.rear = null;
// Execute loop until when more than one node in linked list
while (auxiliary.next != auxiliary)
{
// Used to find n-th node
counter = 1;
while (counter != n)
{
// Get current node
back = auxiliary;
// Visit to next node
auxiliary = auxiliary.next;
counter++;
}
// Segregating n-th position node
back.next = auxiliary.next;
// Visit to next node
auxiliary = back.next;
}
process.stdout.write("\n Size : " + size + " N : " + n + " \n");
// Display last remaining node
process.stdout.write(" Josephus Position " + auxiliary.data + " \n");
cll.head = auxiliary;
cll.rear = auxiliary;
}
}
function main()
{
var task = new JosephusCircle();
// Number of element in circle
var size = 10;
var n = 4;
task.josephusPosition(size, n);
n = 6;
task.josephusPosition(size, n);
}
main();
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
# Python 3 Program
# Josephus circle using circular linked list
# Linked list Node
class LinkNode :
def __init__(self, data) :
# Set node value
self.data = data
self.next = None
# Define Circular List
class CircularList :
def __init__(self) :
self.head = None
self.rear = None
# Add node in circular linked list
def addNode(self, data) :
node = LinkNode(data)
if (self.head == None) :
# First node of linked list
self.head = node
else :
# Add new node at last position
self.rear.next = node
# Connect the first node to the last
node.next = self.head
# Get new last node
self.rear = node
class JosephusCircle :
# Implement josephus circle in circular linked list
def josephusPosition(self, size, n) :
if (n <= 0) :
return
if (n == 1) :
# Base case
print(" Josephus Position ", size ," ")
return
cll = CircularList()
i = 1
# Construct linked list
while (i <= size) :
cll.addNode(i)
i += 1
# Define some auxiliary variables
auxiliary = cll.head
back = cll.head
counter = 0
cll.head = None
cll.rear = None
# Execute loop until when more than one node in linked list
while (auxiliary.next != auxiliary) :
# Used to find n-th node
counter = 1
while (counter != n) :
# Get current node
back = auxiliary
# Visit to next node
auxiliary = auxiliary.next
counter += 1
# Segregating n-th position node
back.next = auxiliary.next
# Visit to next node
auxiliary = back.next
print("\n Size : ", size ," N : ", n ," ")
# Display last remaining node
print(" Josephus Position ", auxiliary.data ," ")
cll.head = auxiliary
cll.rear = auxiliary
def main() :
task = JosephusCircle()
# Number of element in circle
size = 10
n = 4
task.josephusPosition(size, n)
n = 6
task.josephusPosition(size, n)
if __name__ == "__main__": main()
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
# Ruby Program
# Josephus circle using circular linked list
# Linked list Node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
# Set node value
self.data = data
self.next = nil
end
end
# Define Circular List
class CircularList
# Define the accessor and reader of class CircularList
attr_reader :head, :rear
attr_accessor :head, :rear
def initialize()
self.head = nil
self.rear = nil
end
# Add node in circular linked list
def addNode(data)
node = LinkNode.new(data)
if (self.head == nil)
# First node of linked list
self.head = node
else
# Add new node at last position
self.rear.next = node
end
# Connect the first node to the last
node.next = self.head
# Get new last node
self.rear = node
end
end
class JosephusCircle
# Implement josephus circle in circular linked list
def josephusPosition(size, n)
if (n <= 0)
return
end
if (n == 1)
# Base case
print(" Josephus Position ", size ," \n")
return
end
cll = CircularList.new()
i = 1
# Construct linked list
while (i <= size)
cll.addNode(i)
i += 1
end
# Define some auxiliary variables
auxiliary = cll.head
back = cll.head
counter = 0
cll.head = nil
cll.rear = nil
# Execute loop until when more than one node in linked list
while (auxiliary.next != auxiliary)
# Used to find n-th node
counter = 1
while (counter != n)
# Get current node
back = auxiliary
# Visit to next node
auxiliary = auxiliary.next
counter += 1
end
# Segregating n-th position node
back.next = auxiliary.next
# Visit to next node
auxiliary = back.next
end
print("\n Size : ", size ," N : ", n ," \n")
# Display last remaining node
print(" Josephus Position ", auxiliary.data ," \n")
cll.head = auxiliary
cll.rear = auxiliary
end
end
def main()
task = JosephusCircle.new()
# Number of element in circle
size = 10
n = 4
task.josephusPosition(size, n)
n = 6
task.josephusPosition(size, n)
end
main()
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
/*
Scala Program
Josephus circle using circular linked list
*/
// Linked list Node
class LinkNode(var data: Int , var next: LinkNode)
{
def this(data: Int)
{
this(data, null);
}
}
// Define Circular List
class CircularList(var head: LinkNode , var rear: LinkNode)
{
def this()
{
this(null, null);
}
// Add node in circular linked list
def addNode(data: Int): Unit = {
var node: LinkNode = new LinkNode(data);
if (this.head == null)
{
// First node of linked list
this.head = node;
}
else
{
// Add new node at last position
this.rear.next = node;
}
// Connect the first node to the last
node.next = this.head;
// Get new last node
this.rear = node;
}
}
class JosephusCircle
{
// Implement josephus circle in circular linked list
def josephusPosition(size: Int, n: Int): Unit = {
if (n <= 0)
{
return;
}
if (n == 1)
{
// Base case
print(" Josephus Position " + size + " \n");
return;
}
var cll: CircularList = new CircularList();
var i: Int = 1;
// Construct linked list
while (i <= size)
{
cll.addNode(i);
i += 1;
}
// Define some auxiliary variables
var auxiliary: LinkNode = cll.head;
var back: LinkNode = cll.head;
var counter: Int = 0;
cll.head = null;
cll.rear = null;
// Execute loop until when more than one node in linked list
while (auxiliary.next != auxiliary)
{
// Used to find n-th node
counter = 1;
while (counter != n)
{
// Get current node
back = auxiliary;
// Visit to next node
auxiliary = auxiliary.next;
counter += 1;
}
// Segregating n-th position node
back.next = auxiliary.next;
// Visit to next node
auxiliary = back.next;
}
print("\n Size : " + size + " N : " + n + " \n");
// Display last remaining node
print(" Josephus Position " + auxiliary.data + " \n");
cll.head = auxiliary;
cll.rear = auxiliary;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: JosephusCircle = new JosephusCircle();
// Number of element in circle
var size: Int = 10;
var n: Int = 4;
task.josephusPosition(size, n);
n = 6;
task.josephusPosition(size, n);
}
}
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
/*
Kotlin Program
Josephus circle using circular linked list
*/
// Linked list Node
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.next = null;
}
}
// Define Circular List
class CircularList
{
var head: LinkNode ? ;
var rear: LinkNode ? ;
constructor()
{
this.head = null;
this.rear = null;
}
// Add node in circular linked list
fun addNode(data: Int): Unit
{
var node: LinkNode ? = LinkNode(data);
if (this.head == null)
{
// First node of linked list
this.head = node;
}
else
{
// Add new node at last position
this.rear?.next = node;
}
// Connect the first node to the last
node?.next = this.head;
// Get new last node
this.rear = node;
}
}
class JosephusCircle
{
// Implement josephus circle in circular linked list
fun josephusPosition(size: Int, n: Int): Unit
{
if (n <= 0)
{
return;
}
if (n == 1)
{
// Base case
print(" Josephus Position " + size + " \n");
return;
}
var cll: CircularList = CircularList();
var i: Int = 1;
// Construct linked list
while (i <= size)
{
cll.addNode(i);
i += 1;
}
// Define some auxiliary variables
var auxiliary: LinkNode ? = cll.head;
var back: LinkNode ? = cll.head;
var counter: Int ;
cll.head = null;
cll.rear = null;
// Execute loop until when more than one node in linked list
while (auxiliary?.next != auxiliary)
{
// Used to find n-th node
counter = 1;
while (counter != n)
{
// Get current node
back = auxiliary;
// Visit to next node
auxiliary = auxiliary?.next;
counter += 1;
}
// Segregating n-th position node
back?.next = auxiliary?.next;
// Visit to next node
auxiliary = back?.next;
}
print("\n Size : " + size + " N : " + n + " \n");
// Display last remaining node
print(" Josephus Position " + auxiliary!!.data + " \n");
cll.head = auxiliary;
cll.rear = auxiliary;
}
}
fun main(args: Array < String > ): Unit
{
var task: JosephusCircle = JosephusCircle();
// Number of element in circle
var size: Int = 10;
var n: Int = 4;
task.josephusPosition(size, n);
n = 6;
task.josephusPosition(size, n);
}
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
/*
Swift 4 Program
Josephus circle using circular linked list
*/
// Linked list Node
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.next = nil;
}
}
// Define Circular List
class CircularList
{
var head: LinkNode? ;
var rear: LinkNode? ;
init()
{
self.head = nil;
self.rear = nil;
}
// Add node in circular linked list
func addNode(_ data: Int)
{
let node: LinkNode? = LinkNode(data);
if (self.head == nil)
{
// First node of linked list
self.head = node;
}
else
{
// Add new node at last position
self.rear!.next = node;
}
// Connect the first node to the last
node!.next = self.head;
// Get new last node
self.rear = node;
}
}
class JosephusCircle
{
// Implement josephus circle in circular linked list
func josephusPosition(_ size: Int, _ n: Int)
{
if (n <= 0)
{
return;
}
if (n == 1)
{
// Base case
print(" Josephus Position ", size ," ");
return;
}
let cll: CircularList = CircularList();
var i: Int = 1;
// Construct linked list
while (i <= size)
{
cll.addNode(i);
i += 1;
}
// Define some auxiliary variables
var auxiliary: LinkNode? = cll.head;
var back: LinkNode? = cll.head;
var counter: Int = 0;
cll.head = nil;
cll.rear = nil;
// Execute loop until when more than one node in linked list
while (!(auxiliary!.next === auxiliary))
{
// Used to find n-th node
counter = 1;
while (counter != n)
{
// Get current node
back = auxiliary;
// Visit to next node
auxiliary = auxiliary!.next;
counter += 1;
}
// Segregating n-th position node
back!.next = auxiliary!.next;
// Visit to next node
auxiliary = back!.next;
}
print("\n Size : ", size ," N : ", n ," ");
// Display last remaining node
print(" Josephus Position ", auxiliary!.data ," ");
cll.head = auxiliary;
cll.rear = auxiliary;
}
}
func main()
{
let task: JosephusCircle = JosephusCircle();
// Number of element in circle
let size: Int = 10;
var n: Int = 4;
task.josephusPosition(size, n);
n = 6;
task.josephusPosition(size, n);
}
main();
Output
Size : 10 N : 4
Josephus Position 5
Size : 10 N : 6
Josephus Position 3
Time Complexity
The time complexity of solving the Josephus problem using a circular linked list is O(size * n), where size is the number of people and n is the elimination parameter. In each iteration, the program traverses the circular linked list to find the nth person.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment