Update appNew update is available. Click here to update.

Josephus Problem

Kushleen Waraich
Last Updated: Dec 20, 2022
MEDIUM
Josephus Problem

Introduction

Josephus' problem is a mathematical counting-out problem and claims that it originates from an incident in the first century when the Jewish revolted against Rome. When they saw that they couldn't stand against the Roman army, Historian Flavius Josephus and his 39 comrades decide to commit suicide rather than surrender to the enemy.

They agreed that they would form a circle, and each person is designated a number. Then, they would kill every seventh person moving clockwise. The one last person to survive will kill himself. Josephus had already calculated that by standing where he was, he himself will be the last person to survive. As per the legend, he survived and joined the Romans.

Josephus Problem Using a Linked List

It is an easy method to solve this problem. We create a linked list of all the values from 1 to n, then for a given n and k. Then we traverse the link up to k nodes and then delete the kth node. We again start from the next node of the last deleted node and traverse the link up to the following k nodes and then delete the kth node. We repeat this process until the linked list has just one node. 

Algorithm of approach using Linked List

  • Create a linked list or take it as input from the input.
     
  • Take the starting position and k as input from the user.
     
  • Define a function to remove the kth node from the linked list. It takes the list, k, and the starting index as arguments. This function makes a recursive call after every removal, with the new starting position.
     
  • The above function stops making further calls after reaching the base case when the linked list has only one element.
     

Implementation of Approach using Linked List

#include <bits/stdc++.h>
using namespace std;
//Function to return safe position, it takes n, k and starting position as arguments.
void josephus(vector<int> numbers, int k, int startpos)
{
    if(numbers.size()==1)
    {
        //Base case.
        cout<<numbers[0]<<endl;
     return;
    }
    //To find the first number to be removed.
    startpos = ((startpos + k) % numbers.size());
    //Removing the number.
    numbers.erase(numbers.begin() + startpos);
    //Recursive call with updated arguments
    josephus(numbers, k , startpos);  
}
//Driver Function.
int main()
{
    int n, k, startpos;
    cout<< "Enter values for n, k and starting position."<<endl;
    cin>>n>>k>>startpos;
    k--;
    //Declaring a vector.
    vector<int> numbers;
    for (int i = 1; i <= n; i++) 
    {
        numbers.push_back(i);
    }
    //Calling the function that calculates the safe position.
    josephus(numbers, k, startpos);
}

Input-

6 3 0

 

Output-

Enter values for n, k and starting position.
1


Complexity Analysis

 

The time complexity of this approach is O(N).

The space complexity of this approach is O(N), as we make recursive calls.

Problem statement of Josephus's problem

In modern mathematics, the problem statement for Josephus's problem is as follows-

N people are standing in a circle waiting to get executed, and counting starts from a certain point in the circle, in a specific direction, either clockwise or counterclockwise. After skipping k people, the next person gets executed. 

The exact process is repeated for the remaining people, starting with the next person from the last executed person. We again skip k people to execute the next person. We do this until only one person is left.

We need to find that person's position who survives in the initial circle with n people. To read more and understand the problem statement, you can visit this link to check results with different combinations of n and k.

Explanation of the Josephus problem

Let’s see a simple example of if we start with a group of 6 people and execute every second person while moving clockwise in the circle-

If we start with a person marked as 1, after completing one round, 1, 3, 5 survive, and 2, 4, 6 get executed. Now, we have the same problem with n =3. In this round, 3 gets executed, 1 and 5 are left. In the next round, 1 gets executed, and 5 survives, as we need to skip the person next to the last executed person, i.e., 3.

Josephus Problem


Now, since we have thoroughly understood the problem and how it works, let’s move to learning how to write a program that can take n and k as input and tell us the last number remaining in a circle of n number if we start deleting every kth number -

The basic approach to solving this problem is using recursion and the second approach uses a Linked list to solve it. Let's discuss these in detail.

Approach to Solve the Josephus Problem Iteratively

Add each value in the list from 1 to N. We will begin with start = 0 and k = 1(0-indexing). 

Example step 1

The second person (the element at index 1) will be executed(killed). It is also taken off the list.

Example Step 2

The new counting will start at index 1, and since index one was just dead, index 2 (person number 3) is now at index 1, and counting will begin from this point. Currently, there are five persons, counting from position 1 (person number 3), and the person in position K (2-index) will be killed, i.e., person 4.

Example step 3

 

Now that person number 4 at 2-index has been executed, there are only 4 people left, and person number 5 at 3-index has moved to 2-index. And this is where the count begins. Person 6(the element at index 1) will be executed(killed).

Example Step 4

Person number 3 has been executed, only two people are left, and person number 5 moved to 1-index.

Example Step 5

The first person (the element at index 1) will be executed(killed). It is also taken off the list, and the winner is Person 5.

Example Step 6

Algorithm

  1. Create an array arr[] of size N with the initial value set to 1, and initialize the variables:  size, start, and end with the values 1, 0, and 0, respectively.
     
  2. Run a while loop from start = 0 to start< size of array(N):

    1. Run a while loop from size = 0 to size <= K(Number of People to be skipped).

      1. Increment end by 1 and then perform modulo N in the next step.
         
      2. If arr[end] = 1, add one to size by 1.
         
    2. Set size = 1, arr[end] = 0, and increment start and end by one and end = end % N.
       
    3. Run a while loop till arr[end] = 0 and increment end by one.
       
  3. Return size + 1 as a result.

 

Implementation

#include <bits/stdc++.h>

using namespace std;

int Josephus(int, int);

int Josephus(int N, int K) {
  K--;
  int arr[N];

  // Makes all the N people alive
  for (int i = 0; i < N; i++) {
    arr[i] = 1;
  }

  int start = 0, end = 0,
    // start = 0 means the sword is in hand of 1st person.
    size = 1;

  // till N-1 person dies.
  while (start < (N - 1)) {

    while (size <= K) {
      end++;

      end = end % N;

      if (arr[end] == 1) {
        // Updating the number of persons alive.
        size++;
      }
    }

    // size= 1 for next use.
    size = 1;

    // The person at the position of 'end' gets killed
    arr[end] = 0;

    // Updating the no. of killed persons.
    start++;
    end++;

    // Checking the overflow of Index.
    end = end % N;

    while (arr[end] == 0) {
      end++;

      // Checking the overflow of Index.
      end = end % N;
    }
  }

  // Output is the position of the last alive person;
  return end + 1;
}

// Driver code
int main() {
  int n = 18, k = 2;
  cout << Josephus(n, k);
  return 0;
}

 

Output-

5

 

Complexity Analysis

 

Time Complexity: We are using the nested while to traverse the list and execute the persons, so the time complexity of the program is O(N2).

Space Complexity: The space complexity is O(N) since we use the extra space to store a list of people.

Approach to Solve the Josephus Problem Recursively

The basic approach to solve this problem is to find a step that could be called recursively after each execution. So if we have n numbers and skip k numbers while deletion, after each deletion, the number of numbers decreases by 1, i.e., we are left with n-1 numbers, so we call the recurring step for n-1 and k.

But, here, we need to keep track of the safe position (last remaining number) in the initial circle. Since the starting point, after the first deletion, is the next number to the number deleted first, if the number at the kth place gets deleted, the k+1th position will be for the recursion step with parameters  n-1, k. So, to keep track of the shift of k%n+1, it is added in each recursion step.

The base case for this recursion occurs when n=1; in that case, the safe position is 1. With the above explanation, we can frame the recursive structure of the problem as

josephus(n,k) = (josephus(n-1,k)+k-1)%n+1

And the base case occurs for n=1 as

josephus(1,k)=1

Algorithm

  • Take n and k as input from the user.
     
  • Call the Josephus function for n and k.
     
  • Recursively call Josephus with the recursive step as follows- 
     

josephus(n,k) = (josephus(n-1,k)+k-1)%n+1, with josephus(1,k)=1 as the base case.

Implementation

#include <bits/stdc++.h>
using namespace std;
//Function to return safe position, it takes n and k as arguments.
int josephus(int n, int k)
{
    if(n==1)
    {
        //Base case.
        return 1;
    }
    else
    {
        //recursive step.
        return (josephus(n-1,k)+k-1)%n+1;
    }
}
//Driver Function.
int main()
{
    int n,k;
    cout<< "Enter values for n and k."<<endl;
    cin>>n>>k;
    cout<< "The safe position is "<<josephus(n,k);
    return 0;
}


Input-

6 3 


Output-

Enter values for n and l.
The safe position is 1 

 

Complexity Analysis


The time complexity of this approach is O(N).

The space complexity of this approach is O(N), as we make N recursive calls.

Special Case for K=2

A lot of research happened on Josephus's problem over the years. Numerous mathematicians have claimed many theorems and corollaries about exceptional cases, but the most enticing case is k=2. You can visit here to read an article discussing this particular case in detail.

Frequently Asked Questions

What is Josephus Problem?

In computer science, the Josephus problem is a modern mathematical problem. According to the problem, N people are standing in a circle waiting to get executed, and counting starts from a certain point in the circle in a specific direction, either clockwise or counterclockwise. After skipping k people, the next person gets executed. 

How do you solve the Josephus Problem?

In programming, we solve Josephus's problem using recursion. We recursively delete the number at the kth position from the start. And keep track of the shift in starting position, thus finding the safe position.

Which type of data structure is suitable to solve the Josephus problem?

We can use a linked list to solve this problem because it is easier to remove the number directly.

Is the Josephus Problem real?

As per the historical reference, it is claimed to be accurate, but more important is that its concept applies to numerous real-life scenarios.

How can we solve the Joseph problem by using a linked list?

There are numerous ways to solve Josephus' problem. One uses simple recursion, and the other uses a linked list to solve it. In the linked list, we recursively delete the kth node. We form a recursive function that takes the linked list, k, and the starting position for every deletion as arguments. 

Conclusion

In this article, we discussed the Josephus problem and how we can solve it-

  • The first method makes recursive calls to find the next number to be deleted after considering the next number to the last deleted number as the starting point for the next call. We also take care of the shift happening with each call by adding k%n +1 in each call.
     
  • The second method uses a linked list to solve this problem. We form a linked list then delete its kth node. We then again call recursion to count and delete the kth node from the last executed node. This way, after traversing the list a few times, we are left with only one node, our solution.
     

Recommended Articles

Also practice some of the questions mentioned below based on linkedlist data structure.

To read more about the recursion or linked list, visit these links- Recursion Linked list. You can also solve problems related to these on CodeStudio. If you liked this blog, share it with your friends!

Check out this article on the special case of Josephus problem where K= 2.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on CodeStudio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.

Was this article helpful ?
5 upvotes