This Python program solves the Josephus Problem using a circular linked list. The Josephus Problem is a theoretical problem related to a certain counting-out game, where people stand in a circle, and every nth person is eliminated until only one person remains.

The Josephus Problem is a famous theoretical problem related to a certain elimination game. In this problem, a group of people stand in a circle, and at each step, a certain number of people are skipped and the next person is eliminated. This process continues until only one person remains. The challenge is to determine the position of the last remaining person.

## Problem Statement

Given the total number of people in the circle and the number of people to be skipped in each step, write a Python program to find the position of the last remaining person in the circle.

## Python Program to Solve Josephus Problem using Linked List

class Node: def __init__(self, data): self.data = data self.next = None class CircularLinkedList: def __init__(self): self.head = None def add_node(self, data): new_node = Node(data) if not self.head: self.head = new_node self.head.next = self.head else: temp = self.head while temp.next != self.head: temp = temp.next temp.next = new_node new_node.next = self.head def remove_node(self, node): if self.head == node: temp = self.head while temp.next != self.head: temp = temp.next temp.next = self.head.next self.head = self.head.next else: temp = self.head prev = None while temp.next != self.head: prev = temp temp = temp.next if temp == node: prev.next = temp.next break def josephus(self, step): temp = self.head while len(self) > 1: count = 1 while count < step: temp = temp.next count += 1 self.remove_node(temp) temp = temp.next def __len__(self): count = 0 temp = self.head while temp: count += 1 temp = temp.next if temp == self.head: break return count def get_survivor(self): return self.head.data def solve_josephus(n, k): cll = CircularLinkedList() for i in range(1, n + 1): cll.add_node(i) cll.josephus(k) return cll.get_survivor() # Input total_people = int(input("Enter the total number of people: ")) skip_count = int(input("Enter the number of people to be skipped: ")) # Output survivor_position = solve_josephus(total_people, skip_count) print(f"The survivor is at position: {survivor_position}")

## How It Works

The program defines a `Node`

class and a `CircularLinkedList`

class to handle the circular linked list data structure. The `josephus`

method simulates the elimination process according to the given step, and the `solve_josephus`

function orchestrates the entire process and returns the position of the survivor.

## Leave a Review