Skip to main content

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

  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>

 // 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.

Last updated on by Kalkicode




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.

New Comment