Posted on by Kalkicode

# 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:

1. Create a circular linked list with the given number of people.
2. 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):
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

1. Create a new circular linked list.
2. 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>

{
int data;
};
// Circular List
struct CircularList
{
};
// Returns a new linked list
struct CircularList *newCLL()
{
// Create dynamic node
struct CircularList *cll = (struct CircularList *) malloc(sizeof(struct CircularList));
if (cll != 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
{
// Create dynamic node
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
void addNode(struct CircularList *cll, int data)
{
{
// First node of linked list
}
else
{
// Add new node at last position
cll->rear->next = node;
}
// Connect the first node to the last
// 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();
for (int i = 1; i <= size; ++i)
{
}
// Define some auxiliary variables
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
*/
{
public int data;
{
// Set node value
this.data = data;
this.next = null;
}
}
// Define Circular List
class CircularList
{
public CircularList()
{
this.rear = null;
}
{
{
// First node of linked list
}
else
{
// Add new node at last position
this.rear.next = node;
}
// Connect the first node to the last
// 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();
for (int i = 1; i <= size; ++i)
{
}
// Define some auxiliary variables
int counter = 0;
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.rear = auxiliary;
}
public static void main(String[] args)
{
// Number of element in circle
int size = 10;
int n = 4;
n = 6;
}
}

#### Output

Size : 10 N : 4
Josephus Position 5

Size : 10 N : 6
Josephus Position 3
#include <iostream>

using namespace std;
/*
C++ Program
Josephus circle using circular linked list
*/
{
public: int data;
{
// Set node value
this->data = data;
this->next = NULL;
}
};
// Define Circular List
class CircularList
{
CircularList()
{
this->rear = NULL;
}
{
{
// First node of linked list
}
else
{
// Add new node at last position
this->rear->next = node;
}
// Connect the first node to the last
// 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();
for (int i = 1; i <= size; ++i)
{
}
// Define some auxiliary variables
int counter = 0;
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.rear = auxiliary;
}
};
int main()
{
// Number of element in circle
int size = 10;
int n = 4;
n = 6;
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
*/
{
public int data;
{
// Set node value
this.data = data;
this.next = null;
}
}
// Define Circular List
public class CircularList
{
public CircularList()
{
this.rear = null;
}
{
{
// First node of linked list
}
else
{
// Add new node at last position
this.rear.next = node;
}
// Connect the first node to the last
// 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();
for (int i = 1; i <= size; ++i)
{
}
// Define some auxiliary variables
int counter = 0;
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.rear = auxiliary;
}
public static void Main(String[] args)
{
// Number of element in circle
int size = 10;
int n = 4;
n = 6;
}
}

#### Output

Size : 10 N : 4
Josephus Position 5

Size : 10 N : 6
Josephus Position 3
<?php
/*
Php Program
Josephus circle using circular linked list
*/
{
public \$data;
public \$next;

function __construct(\$data)
{
// Set node value
\$this->data = \$data;
\$this->next = null;
}
}
// Define Circular List
class CircularList
{
public \$rear;

function __construct()
{
\$this->rear = null;
}
{
{
// First node of linked list
}
else
{
// Add new node at last position
\$this->rear->next = \$node;
}
// Connect the first node to the last
// 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();
for (\$i = 1; \$i <= \$size; ++\$i)
{
}
// Define some auxiliary variables
\$counter = 0;
\$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->rear = \$auxiliary;
}
}

function main()
{
// Number of element in circle
\$size = 10;
\$n = 4;
\$n = 6;
}
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
*/
{
constructor(data)
{
// Set node value
this.data = data;
this.next = null;
}
}
// Define Circular List
class CircularList
{
constructor()
{
this.rear = null;
}
{
{
// First node of linked list
}
else
{
// Add new node at last position
this.rear.next = node;
}
// Connect the first node to the last
// 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();
for (var i = 1; i <= size; ++i)
{
}
// Define some auxiliary variables
var counter = 0;
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.rear = auxiliary;
}
}

function main()
{
// Number of element in circle
var size = 10;
var n = 4;
n = 6;
}
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

def __init__(self, data) :
#  Set node value
self.data = data
self.next = None

#  Define Circular List
class CircularList :

def __init__(self) :
self.rear = None

#  First node of linked list
else :
#  Add new node at last position
self.rear.next = node

#  Connect the first node to the last
#  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
while (i <= size) :
i += 1

#  Define some auxiliary variables
counter = 0
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.rear = auxiliary

def main() :
#  Number of element in circle
size = 10
n = 4
n = 6

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

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

def initialize()
self.rear = nil
end

#  First node of linked list
else
#  Add new node at last position
self.rear.next = node
end

#  Connect the first node to the last
#  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
while (i <= size)
i += 1
end

#  Define some auxiliary variables
counter = 0
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.rear = auxiliary
end

end

def main()
#  Number of element in circle
size = 10
n = 4
n = 6
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
*/
{
def this(data: Int)
{
this(data, null);
}
}
// Define Circular List
{
def this()
{
this(null, null);
}
def addNode(data: Int): Unit = {
{
// First node of linked list
}
else
{
// Add new node at last position
this.rear.next = node;
}
// Connect the first node to the last
// 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;
while (i <= size)
{
i += 1;
}
// Define some auxiliary variables
var counter: Int = 0;
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.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;
n = 6;
}
}

#### Output

Size : 10 N : 4
Josephus Position 5

Size : 10 N : 6
Josephus Position 3
/*
Kotlin Program
Josephus circle using circular linked list
*/
{
var data: Int;
constructor(data: Int)
{
// Set node value
this.data = data;
this.next = null;
}
}
// Define Circular List
class CircularList
{
constructor()
{
this.rear = null;
}
{
{
// First node of linked list
}
else
{
// Add new node at last position
this.rear?.next = node;
}
// Connect the first node to the last
// 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;
while (i <= size)
{
i += 1;
}
// Define some auxiliary variables
var counter: Int ;
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.rear = auxiliary;
}
}
fun main(args: Array < String > ): Unit
{
// Number of element in circle
var size: Int = 10;
var n: Int = 4;
n = 6;
}

#### Output

Size : 10 N : 4
Josephus Position 5

Size : 10 N : 6
Josephus Position 3
/*
Swift 4 Program
Josephus circle using circular linked list
*/
{
var data: Int;
init(_ data: Int)
{
// Set node value
self.data = data;
self.next = nil;
}
}
// Define Circular List
class CircularList
{
init()
{
self.rear = nil;
}
{
{
// First node of linked list
}
else
{
// Add new node at last position
self.rear!.next = node;
}
// Connect the first node to the last
// 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;
while (i <= size)
{
i += 1;
}
// Define some auxiliary variables
var counter: Int = 0;
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.rear = auxiliary;
}
}
func main()
{
// Number of element in circle
let size: Int = 10;
var n: Int = 4;
n = 6;
}
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.

## Comment

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.

Categories
Relative Post