Josephus Problem

Yogesh Kumar
Last Updated: May 13, 2022

Introduction

In the mathematics world, a famous problem called Josephus Problem (or Josephus permutation) is generally a theoretical problem that emphasizes the problem statement in which “N” people are in the waiting state. They’re standing in a circle formation after that. In each of the processes “K-1” person is to skip, and the “Kth” person is to be eliminated.

  1. Statement
  2. Explanation of Statement
  3. Solution
  • Recursive Solution.
  • Non-Recursive Solution.
  • Special Case when K=2.

 

Statement:

We have given two parameters, “N” and “K,” in which “N” denotes the number of people there as numbered as 1 to N, arranged in the form of a circle, and “K” denoting the “Kth” number that is going to get eliminated at every iteration. Then we have to find which numbered person survives at last.

 

 

                              Source:- Josephus Problem

 

We’re going to show this image works for all the soldiers present in the image above and will discuss the detailed explanation of Josephus’ Problem.

Explanation of Statement:

  1. Two parameters “N” and “K,” “N”- number of people in a circle waiting for the state, “K” denotes the “Kth” person eliminated at every iteration.
  2. Counting begins as a “1” position and proceeds around the circle in a specified direction.
  3. After a specified number of people (i.e., K-1) are skipped, the next person is eliminated (i.e., Kth).
  4.  The process is repeated with the rest of the people, starting with the next person, going in the same direction, and skipping the K-1 number of people until only one person remains.

 

E.g.:- N=6 and K=2 

If we start with 6 groups of people standing in the circle, the value of the number at which the person is eliminated is 2 in every count. Let’s understand the concept by this example:-

  1. In the starting, all the people are numbered as 1,2,3,4,5 and 6 all are in the circle.
  2. In the first iteration, people at the even places, 2,4, and 6 were eliminated, and 1,3 and 5 remained in the safe zone.
  3. We have to process the same problem with the change value of N, which becomes 3 now as the K value remains the same.
  4. In the next round, 3 got eliminated, and 1 and 5 survived, and in the next 1 got eliminated, and 5 got survived.
  5. Hence, 5 is the person in the safe zone, and we return our answer to be 5.

 

Solution:

Recursive Sol:

The basic approach for this solution is simply the recursive approach, in which after each elimination, we are calling up for the next N-1 person to perform the task with the same value of K, in that we are making N recursive call for that process and the solution of this problem is going to be solved in O(N).

The base condition for this is for when the number of people is 1. Whatever the value of K does not matter, the answer is always 1 because we have only 1 person and the question itself urges for the solution for the last performance to remain in the safe zone or survival.

Algorithm for the Recursive Sol:

  1. Take the input “N” and “K” from the user.
  2. Recursively call the function for the solution:

 

Code for the problem:

import java.util.Scanner;
//person:- N and kskip:- K
public class josephus {
          static int jp(int person, int kskip){

            // Base condition.
       if(person==1){
                 return 1;
       }
       else{
            return (jp(person-1,kskip)+kskip-1)%person+1;
       }
   }
   public  static  void main(String[] args){
         Scanner sc=new Scanner(System.in);
         int person= sc.nextInt();
       int kskip=sc.nextInt();
       int answer=jp(person,kskip);
       System.out.println(answer);
   }
}

 

Input:

Input takes two integers ‘N’ and ‘K’. Where ‘N’ is the total number of people standing around the circle and ‘K’  number indicates a kth person is killed. 

14 2

 

Output:

Output returns a single integer denoting the position of the last person surviving.  

13

 

Time Complexity: O(n), where n is the number of persons because till there our recursion calls.

Space Complexity: O(n) because the solution uses an internal stack for recursion.

Non - Recursive Sol:

Time Complexity of the problem is O(N), i.e.,“N” no of person, as we iterate and find which person is going to eliminate in each step at last which person remain in the safe zone, we return safe+1, as the naming of a person starts from 1 to N, i.e. is our answer.

Algorithm for the Non-Recursive Sol:

  1. Take input “N” and “K” from the user.
  2. Run a loop from 1 to N(person number i.e. 1 to N).
  3. In each step, we find the eliminated person.
  4. At last, we return the person who remains singly in a circle waiting for the state.
  5. We return safe+1 as the number start as the naming starts from 1 to N.

 

Code for the problem

import java.util.Scanner;
//person:- N and kskip:- K
public class josephus {
   static int jp(int person,int kskip){
       int safe=0;
// Finding the Last survival person after completion of the loop.
       for(int i=1;i<=person;i++){
           safe=(safe+kskip)%i;
       }
       return  safe+1;
   }
   public  static  void main(String[] args){
       Scanner sc=new Scanner(System.in);
       int person= sc.nextInt();
       int kskip=sc.nextInt();
       int answer=jp(person,kskip);
       System.out.println(answer);
   }
}

 

Input:

Input takes two integers ‘N’ and ‘K’. Where ‘N’ is the total number of people standing around the circle and ‘K’ indicates a kth person is killed. 

14 2

 

Output:

Output returns a single integer denoting the position of the last person surviving.  

13

 

Time Complexity: O(n), where n is the number of persons because till there our recursion calls.

Space Complexity: O(n) because the solution uses an internal stack for recursion.

Special Case when K=2:

When the K value is fixed to 2, we can generalize the solution using the mathematical formula for simplicity of the solution, which directly answers in,  O(1). O(1) for calculating the highest power of 2 and O(1) to return the last survival person.

 

E.g.:- K=2 for every value of N.

NAnswer (By Computation)   2^x+L Two*L+1
112^0+01
212^0+01
332^1+13
412^0+01
532^1+13

As we see from the above example, when we get the value of people who remain survive till last is the same as when we split the answer in form of the highest power of 2 and what remains part left “L” when we find . After2*L+1 value comes the same as our answer. 

Approach: Hence, if we find the highest power of 2 given number “N” and subtract from the original number, then what value we get is answers the Josephus problem after finding 2*L+1 value.

Algorithm for the Special Case when K=2 Sol:

  1. Take the value of “N” from the user.
  2. Find the highest power of 2 of the given number “N.”,
  3. Find the remaining part of “N” by L= N- highest power of 2.
  4. Then return the value 2*L+1;

 

Code for the problem:

import java.util.Scanner;
//person:- N and kskip:- K=2 and L= Remain part after highest_power_of_2
public class Josephus {
  static int hpo2(int person){
      person|=person>>1;
      person|=person>>2;
      person|=person>>4;
      person|=person>>8;
      person|=person>>16;

      return person^(person>>1);
  }
  static int jp(int person,int kskip){
      int highest_power_of_2=hpo2(person);
      int L=person-highest_power_of_2;
      return 2*L+1;
  }
  public  static  void main(String[] args){
      Scanner sc=new Scanner(System.in);
      int person= sc.nextInt();
      int answer=jp(person,2);
      System.out.println(answer);
  }
}

 

Input:

Input takes two integers ‘N’ and ‘K’. Where ‘N’ is the total no of persons standing around the circle and ‘K’  number indicates a kth person is killed. 

14 2

 

Output:

Output returns a single integer denoting the position of the last person surviving.  

13

 

Time Complexity: O(1),  we can generalize the solution using the mathematical formula for simplicity precisely two, directly answering in O(1).

Space Complexity: O(1) because we didn’t require any extra space.

 

Frequently Asked Question:

  1. What is Time Complexity for Josephus' Problem Recursive and Non-Recursive?
    O(N)
     
  2. What is Time Complexity for Special Case when K=2 for Josephus Problem?
    O(1)
     
  3. What is the application of Josephus' Problem?
    Test paper generating from general database and Sequence of data in a specific range.

Key Takeaways:

In this blog, we learn different approaches to find the solution of the Josephus Problem, the special cases when K=2, and the Time complexity of each approach, which Codebase and Algorithm design for better understanding.

If you’re confident about the given blog and want to try it, you can submit it on our coding problem code studio Josephus problem. And if you’re going to see its implementation using Linked list, you can check the blog How to solve the Josephus Problem using Recursion and Linked Lists?

If you are a beginner in coding and want to learn DSA, you can look for our guided path for DSA, which is free! 

Was this article helpful ?
5 upvotes

Comments

No comments yet

Be the first to share what you think