LINK02P09 - Editorial

editorial
, ,
1

Problem Link - Practice - Josephus Problem

Problem Statement -

You need to solve the famous Josephus problem using circular linked list in this section.

There are N people standing in a circle like 1->2->3...->N->1 and there is a knife. Whoever has the knife kills the person next to them and hands over the knife, i.e., if 2 has the knife in 1->2->3->1 then 2 kills 3 and hands over the knife to 1. This process continues until there is only one person left, i.e., there is no one left to kill. This last person is deemed as the winner. Initially the knife is with person 1.

For a given N, you need to determine the winner.

Approach:

The key idea of this solution is to use a circular linked list to efficiently simulate the process of eliminating every second person until one person remains.

  1. Node Structure:

    • A Node contains:
      • value: The data of the node, representing a person.
      • next: A pointer to the next node in the circular list.

  2. LinkedList Class:

    • head: A pointer to the first node in the list.
    • tail: A pointer to the last node in the list.

  3. insertAtEnd(int value):

    • This function adds a new node to the end of the circular linked list.
    • If the list is empty, the new node becomes the head.
    • If the list already has elements, the new node is added after the tail, and then the tail pointer is updated to the new node.
    • The next pointer of the new tail is set to point back to the head, making the list circular.

  4. solveJosephus():

    • This function simulates the elimination process.
    • It continuously removes every second person until only one remains.
    • The loop runs until there is only one node left in the list.
    • It updates the head if the eliminated node is the current head and returns the value of the last remaining node.

Time Complexity:

  • insertAtEnd: O(1) as adding to the end of a circular linked list is a constant-time operation.

  • solveJosephus: O(n) where n is the number of people, as each person must be processed to determine the survivor.

Space Complexity:

  • O(n) for storing n nodes in the circular linked list, each with one value and a pointer to the next node.