How to solve the Josephus Problem using Recursion and Linked Lists?

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

Problem statement of Josephus Problem

In modern mathematics, the problem statement for Josephus 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.

Now, since we have thoroughly understood the problem and how it works, let’s move to learn 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 solve this problem is using recursion and the second approach uses a Linked list to solve it. Let’s discuss these in detail.

The Basic Approach to solving Josephus Problem

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 a 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 for Basic Approach

• 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 for basic approach

#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 k.
The safe position is 1

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

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

Solving Josephus problem using 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

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

Key Takeaways

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.

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.

By: Gorakhnath Yadav