Open In App

Josephus Problem

Last Updated : 12 Jun, 2024
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

There are N people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. 

Given the total number of persons N and a number k which indicates that k-1 persons are skipped and the kth person is killed in a circle. The task is to choose the person in the initial circle that survives.

Examples:

Input: N = 5 and k = 2
Output: 3
Explanation: Firstly, the person at position 2 is killed, 
then the person at position 4 is killed, then the person at position 1 is killed. 
Finally, the person at position 5 is killed. So the person at position 3 survives. 

Input: N = 7 and k = 3
Output: 4
Explanations: The persons at positions 3, 6, 2, 7, 5, and 1 are killed in order, 
and the person at position 4 survives.

Josephus problem using List

The simple approach is to create a list and add all values from 1 to N to it. Create a recursive function that takes a list, start (position at which counting will start), and k ( number of people to be skipped) as an argument. If the size of the list is one i.e. only one person left then return this position. Otherwise, start counting the k person in a clockwise direction from starting position and remove the person at the kth position. Now the person at the kth position is removed and now counting will start from this position. This process continues till only one person is left.

Pseudocode :

Josephus( list , start , k){
   if list.size = 1
       return list[0]
   start = (start + k) % list.size
   list.remove( start )
   return Josephus( list, start, k)
}

Follow the below steps to Implement the idea:

  • Create a vector person and push all the values from 1 to N in person.
  • Recursively eliminate the index element 
    • Erase the element on the position index.
    • Call for (index + k)% size of person. 
    • If size of person = 1, return person[i].

Below is the Implementation of the above approach:

C++
Java Python C# JavaScript

Output
13

Time Complexity: O(N2)
Auxiliary Space: O(N), For recursion stack

Approach to solve Josephus problem iteratively:

Illustration:

N = 5,  k = 2

Add all values from 1 to N in the list. We will call the recursive function with start = 0 and k = 1 (0-indexing)

Now the element at 1-index (person number 2) will be killed. And it is removed from the list. The new counting will begin from 1-index, the person at 1-index killed so now person at 2-index (person number 3) comes to 1-index and counting starts from here now.

Now we have 4 people, counting starting from 1-index (person number 3) and the person at kth (2-index ) position will be killed. 

The person at 2-index (person number 4) was killed so now we have 3 people left and the person (person number 5) at 3-index shifted to 2-index. And counting starts from here.

The person at the 0-index was killed and we have now two-person left in the circle. And the person at 1-index shifted to 0-index i.e. person number 3.

Final counting done and the person at 1-index killed and the only person who is left is at position 3.

Follow the below steps to Implement the idea:

  • Initialize variables num, cnt, and cut with 1, 0, and 0 respectively and an array arr[] of size N with the initial value set as 1.
  • Run a while loop till cnt < N:
    • Run a while loop till num is less than equal to k.
      • Increment cut by one and take modulo by N
      • If arr[cut] = 1 increment num by one.
    •  Set num = 1, arr[cut] = 0 and increment cnt and cut by one and cut = cut % n;
    • Run a while loop till arr[cut] = 0 and increment cut by one.
  • Return cnt + 1 as the required answer.

Below is the Implementation of the above approach:

C++
Java Python C# JavaScript

Output
13

Time Complexity: O(N2)
Auxiliary Space: O(N)

Josephus Problem in Linear Time and Constant Space:

Follow the below steps to Solve the Problem (Approach):

  • Initialize variables i and ans with 1 and 0 respectively.
  • Run a while loop till i <= N:
    • Update ans with (ans + k) % i.
    • Increment i by 1.
  • Return ans + 1 as the required answer.

Below is the Implementation of the above Steps:

C++
C Java Python C# JavaScript

Output
13

Time Complexity: O(N)
Auxiliary Space: O(1)

Josephus Problem using Recursion:

Below is the idea to solve the problem:

The problem has the following recursive structure. josephus(n, k) = (josephus(n – 1, k) + k-1) % n + 1 and josephus(1, k) = 1

After the first person (kth from the beginning) is killed, n-1 persons are left. Make recursive call for Josephus(n – 1, k) to get the position with n-1 persons. But the position returned by Josephus(n – 1, k) will consider the position starting from k%n + 1. So make adjustments to the position returned by Josephus(n – 1, k). 

Below is the Implementation of the above idea.

C++
C Java Python3 C# JavaScript PHP

Output
The chosen place is 13

Time Complexity: O(N)
Auxiliary Space: O(N) the space used in recursion call stack

Please visit set-2: Josephus problem | Set 2 (A Simple Solution when k = 2)


Master DSA and also get 90% fee refund on completing 90% course in 90 days! Take the Three 90 Challenge today.

Step into the Three 90 Challenge – 90 days to push limits, break barriers, and become the best version of yourself! Don't miss your chance to upskill and get 90% refund. What more motivation do you need? Start the challenge right away!


Next Article

Similar Reads

three90RightbarBannerImg