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:

Output:

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:

Java Implementation

C++ Implementation

Python Implementation

Output:

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: