Josephus problem

Problem Statement

There is n number of people standing in a circle. Numbering starts from 1 to n and is in the fixed clockwise direction. In each step, we are supposed to eliminate a person which is at the $k^{th}$ position from the current position such that only one man remains at the end who is to be given freedom.

The counting starts from 1, k-1 people are skipped and $k^{th}$ person is to be removed. Again counting starts from $(k+1)^{th}$ person, k-1 people are skipped and $k^{th}$ person from the current position is removed. This process is repeated until only one man is remaining in the circle.

The input consists of two integers n and k where n is the number of people in the circle and using the k position for eliminating the next person is calculated. k-1 people are skipped from the current position and $k^{th}$ person is to be killed.

The output is an integer greater than zero and less than or equal to n. This integer is the safe position for the person to stand at as only the last person survives.

Constraints

The values of n as well as k are greater than or equal to 1 and are less than or equal to $10^5$.

Constraints:
1 <= n, k <= $10^5$

Example

Let us dive into an example of a Josephus problem.

Input:

n = 5, k = 3

Output:

4

Example Explanation

Initially, 5 people are standing in the circle as follows:

Now starting from $1^{st}$ position we will skip k-1 people and kill the kth person. Out k in the example above is 3 so the person to be killed is 3rd person.

Next, our current becomes the $4^{th}$ person in the circle, we go from 4 to 5 and back to 1 which is $k^{th}$ person is killed.

Now the current is $2^{nd}$ person, we don’t consider $3^{rd}$ person as it is already killed. The next person is $4^{th}$ and $5^{th}$ person is killed.

Again the current is $2^{nd}$ person and we go to $4^{th}$ person and back to $2^{nd}$ person. Thus, $2^{nd}$ person is killed in this step.

Now, only one of the last people is remaining which is the person in the $4^{th}$ position. This is the required output, it is the safe position as $4^{th}$ person will be the last one remaining to survive.

Approach 1: Recursive Structure (Code in Java, Python, C++)

A simple approach is to use recursion. Recursively we call the Josephus problem() function for eliminating a person from the group at a certain position and decrementing the number of people in the group with each call until the last person is left. There are n people in the group, and $k^{th}$ person is to be killed from the current position. Once the first person is killed, n-1 people are left. So we call the Josephus function for n-1 and k. Then from n-1, k to n-2,k and so on until n==1 which forms our base case.

The position returned by the Josephus function when n equals 1 is 1, irrespective of the value of k as there is only one person left. So this becomes our base condition for the recursive function. Now we are required to find the formula for the recursive call. Let us apply brute force to find the values for n from 1 to 10 and k as well from 1 to 10.

As it is a recursive function we will be calling it for smaller operations i.e. $J_{(n-1,k)}$. The result that we get from the smaller problem needs to be adjusted. To make adjustments in the position we add k-1 to it. As we are adding, the position may be greater than n which may cause the error. Also, all the people are standing in a circle. So, we simply take modules to get an effective position. As we are using one-indexing i.e. position of the first person starts from one we add 1 to the result. The pattern so formed is

$J_{n,k} = ((J_{(n-1,k)} + k-1) mod n) + 1$

Let’s take the same example of n=5 and k=3, using the above formula:
n=1, k=3:
$J_{(n,k)} = J_{(1,3)} = 1$

n=2, k=3:
$J_{(2,3)} = (J_{(1,3)} + (3-1)) \% 2 + 1 = 2$

n=3, k=3:
$J_{(3,3)} = (J_{(2,3)} + (3-1)) \% 3 + 1 = 2$

n=4, k=3:
$J_{(4,3)} = (J_{(3,3)} + (3-1)) \% 4 + 1 = 1$

n=5, k=3:
$J_{(5,3)} = (J_{(4,3)} + (3-1)) \% 5 + 1 = 4$

Recursively, we go from 5 to 1 and reach to the solution which is the same as the brute force approach. Let us apply the same formula in the algorithm:

if(n==1) return 1;
else{
    return ((josephusProblem(n-1,k) + k - 1) % n) + 1;
}

Java Implementation

import java.util.*;
public class Main{
    public static void main(String args[]) {
        // taking user input
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter number of people: ");
      int n = sc.nextInt();
      System.out.println("Enter value of k: ");
      int k = sc.nextInt();

      // returning answer
      int ans = josephusProblem(n,k);
      System.out.println("The safe position for the Josephus problem is: "+ans);
    }

    // recursive method to find the last person's position
    static int josephusProblem(int n, int k){
        if n is 1 irrespective of the value of k the last remaining person is 1
        if (n == 1)
            return 1;
        // recursively calling the function with n-1 and adjusting the position
        else
            return (josephusProblem(n - 1, k) + k - 1) % n + 1;
    }
}

C++ Implementation

#include <iostream>

using namespace std;

// recursive function to find the position
int josephusProblem(int n, int k){
    // if n is 1 irrespective of the value of k the answer is 1
    if (n == 1)
        return 1;
    // recursively calling the function with n-1 and adjusting the position
    else
        return (josephusProblem(n - 1, k) + k - 1) % n + 1;
}
int main()
{
    // taking user input
    cout << "Enter number of people: ";
    int n, k;
    cin >> n;
    cout << "Enter value of k: ";
    cin >> k;

    // returning the answer
    int ans = josephusProblem(n,k);
    cout << "The safe position for the Josephus problem is: " << ans;
}

Python Implementation

# recursive function to find the position 
def josephusProblem(n, k):
    # if n is 1, irrespective of k the answer is 1
    if (n==1):
        return 1
    # reducing the problem to n-1 and adjusting the position
    else:
        return (josephusProblem(n -1, k) + k - 1) % n + 1

# taking user input
n = int(input("Enter the number of people: "))
k = int(input("Enter the value of k: "))

# returning solution
ans = josephusProblem(n,k)
print("The safe position for the Josephus problem is: ",ans)

Output:

Enter the number of people: 
32
Enter the value of k: 
32
The safe position for the Josephus problem is: 27

Complexity Analysis

Time Complexity

The time complexity for the recursive solution is **O(n)**as if n is greater than 1, the Josephus problem function is called by decreasing the value of n by 1 i.e. n-1 until n is not equal to 1. The function will be called as – josephusProblem(n, k), josepusProblem(n-1, k), josephusProblem(n-2, k) …, josephusProblem(2, k), josephusProblem(1, k). Thus, it is called n times and the time complexity for the same is O(n).

Space Complexity

The space complexity for this solution is O(n) as the call sequence which led to this state would be f(n)->f(n-1)->f(n-2)->...->f(1). The result of these are stored in the stack frames in the memory and when f(n) is called it calls all the previous function calls and then calculates the current value and returns it. After which it is removed from the memory.

Approach 2: Using List (Code in Java, Python, C++)

Another approach is using lists which is very much similar to the brute force approach. In this approach, we iteratively remove the person at the $k^{th}$ position from the current position. We first change the value of the current position as pos = (pos+k-1)%n, remove the person at the current position, and decrement the value of n until our n is not equal to 1. In other words, we remove the element of the list at the index pos.

The algorithm for the same is as follows:

// create a list and insert all the positions from 1 to n.
List list = [1, 2, .. , n]
while(n!=1){
    pos = (pos+k-1)%n;
    person.remove(pos);
    n-=1;
}
return person.get(pos);

**Note: **
Here, n is the index in the list respectively.
Let us see an example where n = 8 and k = 3.

The list initially is as follows:
[1, 2, 3, 4, 5, 6, 7, 8]

In the first iteration

Thus at the end, only $7^{th}$ position is remaining.

Java Implementation

import java.util.*;
public class Josephus {
    static int josephusProblem(int n, int k) {
        // creating a list of n people
        List<Integer> person = new ArrayList<>();
        for(int i =0;i<n;i++){
            person.add(i+1);
        }
        int n1 = n;
        int pos = 0;

        // in each iteration one person is eliminated
    // until only one person is left
        while(n1!=1){

            // position of next person to be killed
            pos = (pos+k-1)%n1;
            person.remove(pos);
            n1-=1;

        }

        // returning the position of last person remaining
        pos = pos%n1;
        return person.get(pos);
    }
    public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);

      // taking user input
      System.out.println("Enter number of people: ");
      int n = sc.nextInt();
      System.out.println("Enter value of k: ");
      int k = sc.nextInt();

      // returning answer   
      int ans = josephusProblem(n,k);
      System.out.println("The safe position for the Josephus problem is: "+ans);
    }
}

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int josephusProblem(int n, int k){

    // creating a list of n people
    vector<int> person;
    for(int i =0;i<n;i++){
        person.push_back(i+1);
    }
    int n1 = n;
    int pos = 0;

    // in each iteration one person is eliminated
    // until only one person is left
    while(n1!=1){
        // position of next person to be killed
        pos = (pos+k-1)%n1;
        person.erase(person.begin()+pos);
        n1-=1;
    }

    // returning the position of last person remaining
    pos = pos%n1;
    return person.at(pos);
}
int main()
{
    // taking user input
    cout << "Enter number of people: ";
    int n, k;
    cin >> n;
    cout << "Enter value of k: ";
    cin >> k;

    // returning answer
    int ans = josephusProblem(n,k);
    cout << "The safe position for the Josephus problem is: " << ans;
}

Python Implementation

def josephusProblem(n, k):
    # creating a list of n people
    person = []
    for i in range(0,n):
        person.append(i+1)
    n1 = n
    pos = 0

    # in each iteration one person is eliminated
    # until only one person is left
    while(n1!=1):
        # position of next person to be killed
        pos = (pos+k-1)%n1
        person.pop(pos)
        n1-=1

    # returning the position of the last person remaining
    pos = pos%n1;
    return person[pos]

# taking user input      
n = int(input("Enter number of people: "))
k = int(input("Enter value of k: "))

# returning answer
ans = josephusProblem(n,k)
print("The safe position for the Josephus problem is: ",ans)

Output:

Enter the number of people: 
34
Enter the value of k: 
6
The safe position for the Josephus problem is: 28

Complexity Analysis

Time Complexity

The time complexity for this algorithm is O(n) as we are iterating through the loop for each person in the circle.

Space Complexity

In the algorithm above we are using an extra list for saving all the positions in a list which accounts for the additional space and thus occupies O(n) space.

Conclusion

• There are two approaches usually used to solve the Josephus problem.
• The first one is using recursion, n=1 is the base condition and we return 1. The formula for the rest of the cases is $J_{(n,k)} = ((J_{(n-1,k)} + k – 1) \% n) + 1$.
• The other solution is using the list. We first insert all the positions in the list and remove all the people at the $k^{th}$ position until only one person is remaining $k^{th}$.

FAQs

Q: Which data structure is used to solve the Josephus problem?

A: The List data structure is used to solve the problem usually. It is used to store all the positions from 1 to n. We can also use recursion to solve the problem.

Q: What is the brute force approach to solve Josephus’s problem?

A: The Josephus problem can be solved by eliminating the person at the $k^{th}$ position iteratively and recursively until only one person is remaining $k^{th}$.

Q: What is the best complexity we can achieve and use which approach?

A: We can have O(n) time complexity and O(n) space complexity at least using both the approaches i.e. the list as well as the recursion approach.

Q: What is the special case of this problem?

A: k=2 is the special case of this problem. It becomes very much easier to solve it with less amount of recursive calls as well as lesser time complexity.

• case I: n is even
  If n is even then all the even positions i.e. 2, 4, 6, …, n-2, and n are eliminated as k is 2 and the problem is remaining only for n/2 number of positions i.e. 1, 3, …, n-1. Also, we are required to adjust the positions by shifting as follows:
  $J_{(2*n),2)} = 2 * J_{(n,2)} – 1$
• case II: n is odd
  Similarly, when n is odd, all the even numbers i.e. (n-1)/2 are again crossed out. The remaining problem is for (n+1)/2, taking into account the shift of positions we obtain the following formula:
  $J_{(2*n+1),2)} = 2 * J_{(n,2)} + 1$

Common formula
We can rather use a simpler formula, which is applicable for both cases:
$J_{(n,2)} = 1 + 2 * (n – 2^{(floor(log2(n)))})$