Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Example
1.3.
Explanation
2.
Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
2.3.
Implementation in Python
2.3.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is the time complexity of the Josephus Circle Implementation using STL Lists?
3.2.
Can we solve the Josephus Circle Implementation problem using recursion?
3.3.
What is the significance of STL?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Josephus Circle Implementation Using STL List

Introduction

Have You ever heard about the “Game of Death in a Circle” Puzzle? Have you ever tried to solve that Deadly Puzzle? This is an exciting problem commonly known as the Josephus Circle problem. Do you know how to implement this?

                                                  
                                                                                       Source

Don’t worry if you don’t know, as we will discuss the Implementation of the Josephus Circle problem using STL lists. At first, we will discuss the problem and its solution in detail then we will move to the Implementation part of the solution. So, without further ado, let’s start.

Problem Statement

People are gathered in a circle, awaiting execution. Counting begins at a specific point on the circle and moves in one particular direction around it. The following person is executed when a certain number of individuals have been skipped. The practice is repeated with the remaining persons, beginning with the next person, proceeding in the same direction, and skipping the same amount of individuals until only one person is left, who is then released.

The task is to find a place in the initial circle to escape execution, given the number of personsstarting pointdirection, and number to be skipped.

This puzzle's "regular" variation involves skipping one person at a time. For the time being, let's concentrate on this.

Also read - Merge sort in linked list

Example

Here is an example of the Josephus Circle Implementation Problem.

With 13 persons in the circle, here's a visual representation of how the puzzle functions:

                                               

                                                                                  Source

The following is the order of deaths: 2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3; position 11 is the winner.

In general, how can we readily select the winner? Let's get started with the problem discussed in detail.

Explanation

Let's break the problem into smaller ones to see the solution to the Josephus Circle Implementation problem. We will find a general formula for the winner of this deadly circle.

When we have five persons:

                                              

                                                                                    Source

The winner, in this case, is the person at position 3.

When we have six persons:

                                              

                                                                              Source

The winner, in this case, is the person at position 5.

When we have seven persons:

                                              

                                                                           Source

The winner, in this case, is the person at position 5.

  • The first important thing: All winning positions must be Odd numbers. So, the even numbers get eliminated first.
  • The second thing: they appear to continue increasing by two each time until they reset to 1.
     

Here's a list of winning positions we'll be able to obtain by working out different numbers of persons in the Josephus Circle Implementation Problem:

                                                      

When the no of persons is a power of 2, the person in the first position will survive.

The person at 1 is only eliminated if the total number of persons in the circle is odd at any point during its turn. This implies that the last person would not be killed and instead kill the person at 1.

Here comes our formula: In terms of m, for the position. The position of the last person standing is 2m+1 for n = 2k + m (with the maximum possible number k, providing that m is nonnegative).

Let us now apply this to Josephus himself.

Because 40 other soldiers accompanied Josephus, his n value was 41. This produces a value of 32 for 2k and 9 for m. In order to be rescued, Josephus must sit in position 2m+1 = 2(9)+1 = 19.

Approach

We are using the list container based on the idea of a circular list for our solution.

Algorithm

Let’s begin with the algorithm of the Josephus Circle Implementation Problem.

  • We'll create a circular linked list of size n, with each node's data being the list's position number.
  • Then we'll traverse the list, deleting the mth node each time until there's just one node remaining.
  • Finally, the left node is our solution to the problem.

Implementation in C++

The given code is the Josephus circle implementation in the C++ language using STL lists.

Code

#include <bits/stdc++.h>
using namespace std;
int JosephusCirclePuzzle(int n, int m)
// n is length of the circle, m is count to choose next person
{
    list<int> lst; //using STL container to create a double linked list
    for (int i = 0; i < n; i++)
    {
        lst.push_back(i);
    }
    //declaring iterator for traversing list
    auto count = lst.begin();
    
    while (lst.size() > 1)
    {
        for (int i = 1; i < m; i++)
        {
            count++;
            if (count == lst.end())
            {
                count = lst.begin();
            }
        }
        count = lst.erase(count);
        if (count == lst.end())
        {
            count = lst.begin();
        }
    }
    return lst.front(); // returns the first element of the list
}
//driver  code
int main()
{
    int n, m;
    cout << "enter the values of n and m:\n";
    cin >> n >> m;
    cout << "The last person remaining at position " << JosephusCirclePuzzle(n, m);
}
You can also try this code with Online C++ Compiler
Run Code

Output

Complexity Analysis

Time Complexity: The time complexity of our solution is O(n*m) as we are using a nested loop.

Auxiliary Space: The auxiliary space required for our solution using STL lists is O(n).

Implementation in Python

The given code is the Josephus circle implementation problem in Python language.

Code

class Node:
            def __init__(self, x):
                       self.data = x
                       self.next = None
def JosephusCirclePuzzle(n, m):

           head = Node(1)
           prev = head
           
           for i in range(2, m + 1):
                       prev.next = Node(I)
                       prev = prev.next
            prev.next = head # Connecting last node to first node
            ptr1 = head
            ptr2 = head
            
            # looping till only one node is left
            while (ptr1.next != ptr1):
    
                           # Finding nth node
                             count = 1
                             while (count != n):
                                     ptr2 = ptr1
                                     ptr1 = ptr1.next
                                     count += 1

                              #  Removing the n-th node 
                              ptr2.next = ptr1.next
                              ptr1 = ptr2.next

            print("The Last person remaining at position, "ptr1.data)

#  Driver code
if __name__ == '__main__':
           m = 8
           n = 2
           print("The Size of the circle is ",m)
           print("The count of the person to choose next is ",n)
           JosephusCirclePuzzle(n, m)
You can also try this code with Online Python Compiler
Run Code

Output

Complexity Analysis

Time Complexity: The time complexity of our solution is O(n*m) as we are using a nested loop.

Auxiliary Space: The auxiliary space required for our solution is O(n).

Also see, Rabin Karp Algorithm.

Frequently Asked Questions

What is the time complexity of the Josephus Circle Implementation using STL Lists?

The time complexity of the implementation of Josephus Circle using STL lists is O(n*m). Where n is the size of the circle and m is the count to choose the next person.

Can we solve the Josephus Circle Implementation problem using recursion?

Yes, recursion can be used to solve the Josephus problem. Recursively eliminate the mth position for each iteration until just one person remains.

What is the significance of STL?

The Standard Template Library (STL) is a collection of C++ template classes for famous programming data structures and functions like listsstacks, and arrays. It's a container library with algorithms, iterators, and container classes. It is a parameterized library since it is a generic library.

Conclusion

This blog discussed the deadly puzzle of Josephus. We discussed the Josephus Circle Implementation Problem using the STL lists.

We have discussed:

  • Problem statement of Josephus circle implementation.
  • Example of the given Josephus circle implementation problem.
  • Explanation of the solutions of the Josephus circle implementation.
  • Algorithm for the solution using the linked lists method.
  • Implementation of the Algorithm.
     

This blog is related to linked lists and circular linked lists, so it is advised to check these articles on linked listsadvantages and disadvantages of Linked ListCircular linked lists, Doubly Linked List and many more at Code Studio Library.
 

You can learn more about STL, such as STL in C++, Algorithms in C++ STLContainers in STL, and many more STL lists.
 

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations, and much more!!

We wish you Good Luck! Keep coding and keep reading Ninja!!

Live masterclass