home
Naukri Code 360
expand-more
Library
expand-more
Josephus Problem
Table of contents
1.
Introduction
2.
What is Josephus Problem?
3.
Josephus Problem Using a Linked List
3.1.
Algorithm of approach using Linked List
3.2.
Implementation of Approach using Linked List
3.3.
C++
3.4.
Java
3.5.
Python
3.5.1.
Complexity Analysis
4.
Josephus's Problem Statement
5.
Explanation of the Josephus problem
6.
Approach to Solve the Josephus Problem Iteratively
6.1.
Algorithm
6.2.
Implementation
6.3.
C++
6.4.
Java
6.5.
Python
6.5.1.
Complexity Analysis
7.
Approach to Solve the Josephus Problem Recursively
7.1.
Algorithm
7.2.
Implementation
7.3.
C++
7.4.
Java
7.5.
Python
7.5.1.
Complexity AnalysisThe time complexity of this approach is O(N).
8.
Special Case for K=2
9.
Josephus Problem in Linear Time and Constant Space:
9.1.
Implementation
9.2.
C++
9.3.
Java
9.4.
Python
9.4.1.
Complexity Analysis
10.
Josephus Problem using Recursion:
10.1.
Implementation
10.2.
C++
10.3.
Java
10.4.
Python
10.4.1.
Complexity Analysis
11.
Frequently Asked Questions
11.1.
How do you solve the Josephus Problem?
11.2.
What is the formula for the Josephus problem?
11.3.
What is the binary solution of the Josephus problem?
12.
Conclusion
Last Updated: Aug 8, 2024
Medium

Josephus Problem

Author Kushleen Waraich
6 upvotes
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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

What is Josephus Problem?

In computer science, the Josephus problem is a modern mathematical problem. According to the problem, 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. 

Josephus Problem Using a 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

  • C++
  • Java
  • Python

C++

#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);
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class JosephusProblem {

    static void josephus(List<Integer> numbers, int k, int startpos) {
        if (numbers.size() == 1) {
            // Base case.
            System.out.println(numbers.get(0));
            return;
        }

        // To find the first number to be removed.
        startpos = (startpos + k) % numbers.size();
        // Removing the number.
        numbers.remove(startpos);
        // Recursive call with updated arguments.
        josephus(numbers, k, startpos);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter values for n, k, and starting position:");
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int startpos = scanner.nextInt();

        k--;

        // Declaring a list.
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        // Calling the function that calculates the safe position.
        josephus(numbers, k, startpos);

        scanner.close();
    }
}
You can also try this code with Online Java Compiler
Run Code

Python

def josephus(numbers, k, startpos):
    if len(numbers) == 1:
        # Base case.
        print(numbers[0])
        return

    # To find the first number to be removed.
    startpos = (startpos + k) % len(numbers)
    # Removing the number.
    numbers.pop(startpos)
    # Recursive call with updated arguments.
    josephus(numbers, k, startpos)

# Driver Function.
if __name__ == "__main__":
    n, k, startpos = map(int, input("Enter values for n, k, and starting position: ").split())
    k -= 1

    # Declaring a list.
    numbers = list(range(1, n + 1))

    # Calling the function that calculates the safe position.
    josephus(numbers, k, startpos)
You can also try this code with Online Python Compiler
Run Code

Input-

6 3 0

 

Output-

Enter values for n, k and starting position.
1


Complexity Analysis

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

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

Josephus's Problem Statement

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

Explanation of the Josephus problem


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

Approach to Solve the Josephus Problem Iteratively

Add each value in the list from 1 to N. We will begin with start = 0 and k = 1(0-indexing). 

josephus problem iteratively

The second person (the element at index 1) will be executed(killed). It is also taken off the list.

iteratively josephus problem

The new counting will start at index 1, and since index one was just dead, index 2 (person number 3) is now at index 1, and counting will begin from this point. Currently, there are five persons, counting from position 1 (person number 3), and the person in position K (2-index) will be killed, i.e., person 4.

solve josephus problem iteratively

 

Now that person number 4 at 2-index has been executed, there are only 4 people left, and person number 5 at 3-index has moved to 2-index. And this is where the count begins. Person 6(the element at index 1) will be executed(killed).

josephus problem statement using iteratively

Person number 3 has been executed, only two people are left, and person number 5 moved to 1-index.

josephus problem statement

The first person (the element at index 1) will be executed(killed). It is also taken off the list, and the winner is Person 5.

solve josephus problem

Algorithm

  1. Create an array arr[] of size N with the initial value set to 1, and initialize the variables:  size, start, and end with the values 1, 0, and 0, respectively.
     
  2. Run a while loop from start = 0 to start< size of array(N):

    1. Run a while loop from size = 0 to size <= K(Number of People to be skipped).

      1. Increment end by 1 and then perform modulo N in the next step.
         
      2. If arr[end] = 1, add one to size by 1.
         
    2. Set size = 1, arr[end] = 0, and increment start and end by one and end = end % N.
       
    3. Run a while loop till arr[end] = 0 and increment end by one.
       
  3. Return size + 1 as a result.

Implementation

  • C++
  • Java
  • Python

C++

#include <bits/stdc++.h>

using namespace std;

int Josephus(int, int);

int Josephus(int N, int K) {
  K--;
  int arr[N];

  // Makes all the N people alive
  for (int i = 0; i < N; i++) {
    arr[i] = 1;
  }

  int start = 0, end = 0,
    // start = 0 means the sword is in hand of 1st person.
    size = 1;

  // till N-1 person dies.
  while (start < (N - 1)) {

    while (size <= K) {
      end++;

      end = end % N;

      if (arr[end] == 1) {
        // Updating the number of persons alive.
        size++;
      }
    }

    // size= 1 for next use.
    size = 1;

    // The person at the position of 'end' gets killed
    arr[end] = 0;

    // Updating the no. of killed persons.
    start++;
    end++;

    // Checking the overflow of Index.
    end = end % N;

    while (arr[end] == 0) {
      end++;

      // Checking the overflow of Index.
      end = end % N;
    }
  }

  // Output is the position of the last alive person;
  return end + 1;
}

// Driver code
int main() {
  int n = 18, k = 2;
  cout << Josephus(n, k);
  return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.Arrays;

public class JosephusProblem {

    static int Josephus(int N, int K) {
        K--;
        int[] arr = new int[N];

        // Makes all the N people alive
        Arrays.fill(arr, 1);

        int start = 0, end = 0, size = 1;

        // Till N-1 person dies.
        while (start < (N - 1)) {
            while (size <= K) {
                end++;
                end = end % N;

                if (arr[end] == 1) {
                    // Updating the number of persons alive.
                    size++;
                }
            }

            // Size = 1 for the next use.
            size = 1;

            // The person at the position of 'end' gets killed.
            arr[end] = 0;

            // Updating the number of killed persons.
            start++;
            end++;

            // Checking the overflow of Index.
            end = end % N;

            while (arr[end] == 0) {
                end++;

                // Checking the overflow of Index.
                end = end % N;
            }
        }

        // Output is the position of the last alive person.
        return end + 1;
    }

    // Driver code
    public static void main(String[] args) {
        int n = 18, k = 2;
        System.out.println(Josephus(n, k));
    }
}
You can also try this code with Online Java Compiler
Run Code

Python

def josephus(N, K):
    K -= 1
    arr = [1] * N

    start = end = size = 0

    # Till N-1 person dies.
    while start < N - 1:
        while size <= K:
            end += 1
            end %= N

            if arr[end] == 1:
                # Updating the number of persons alive.
                size += 1

        # Size = 1 for the next use.
        size = 1

        # The person at the position of 'end' gets killed.
        arr[end] = 0

        # Updating the number of killed persons.
        start += 1
        end += 1

        # Checking the overflow of Index.
        end %= N

        while arr[end] == 0:
            end += 1

            # Checking the overflow of Index.
            end %= N

    # Output is the position of the last alive person.
    return end + 1

# Driver code
if __name__ == "__main__":
    n, k = 18, 2
    print(josephus(n, k))
You can also try this code with Online Python Compiler
Run Code

Output-

5

 

Complexity Analysis

Time Complexity: We are using the nested while to traverse the list and execute the persons, so the time complexity of the program is O(N2).

Space Complexity: The space complexity is O(N) since we use the extra space to store a list of people.

Must Read Algorithm Types

Approach to Solve the Josephus Problem Recursively

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

  • 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

  • C++
  • Java
  • Python

C++

#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;
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.Scanner;

public class JosephusProblem {

    static 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.
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter values for n and k:");
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        System.out.println("The safe position is " + josephus(n, k));

        scanner.close();
    }
}
You can also try this code with Online Java Compiler
Run Code

Python

def josephus(n, k):
    if n == 1:
        # Base case.
        return 1
    else:
        # Recursive step.
        return (josephus(n - 1, k) + k - 1) % n + 1

# Driver Function.
if __name__ == "__main__":
    n, k = map(int, input("Enter values for n and k: ").split())
    print("The safe position is", josephus(n, k))
You can also try this code with Online Python Compiler
Run Code


Input-

6 3


Output-

Enter values for n and l.
The safe position is 1

 

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

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

Also check out - Rod Cutting Problem

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.

Must Read Recursion in Data Structure

Josephus Problem in Linear Time and Constant Space:

  • Initialize i = 1 and ans = 0.
  • Execute the following while loop until i = N: 
    ans = (ans + k)% i;
    i=i+1;
  • Return ans + 1;

Implementation

  • C++
  • Java
  • Python

C++

#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)
{
int i = 1, ans = 0;
while (i <= N) {
 ans = (ans + k) % i;
 i++;
}
return ans + 1; //answer
}
// 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;
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.Scanner;

public class JosephusProblem {

    static int josephus(int N, int k) {
        int i = 1, ans = 0;
        while (i <= N) {
            ans = (ans + k) % i;
            i++;
        }
        return ans + 1; // answer
    }

    // Driver function
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter values for n and k:");
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        System.out.println("The safe position is " + josephus(n, k));

        scanner.close();
    }
}
You can also try this code with Online Java Compiler
Run Code

Python

def josephus(N, k):
    i = 1
    ans = 0
    while i <= N:
        ans = (ans + k) % i
        i += 1
    return ans + 1  # answer

# Driver function
if __name__ == "__main__":
    n, k = map(int, input("Enter values for n and k: ").split())
    print("The safe position is", josephus(n, k))
You can also try this code with Online Python Compiler
Run Code


Input-

6 3


Output-


Enter values for n and k.
6 3
The safe position is 1

 

Complexity Analysis

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

The space complexity of this approach is O(1).

Josephus Problem using Recursion:

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

Implementation

  • C++
  • Java
  • Python

C++

#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;
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.Scanner;

public class JosephusProblem {

    static 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
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter values for n and k:");
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        System.out.println("The safe position is " + josephus(n, k));

        scanner.close();
    }
}
You can also try this code with Online Java Compiler
Run Code

Python

def josephus(n, k):
    if n == 1:
        # Base case
        return 1
    else:
        # Recursive step
        return (josephus(n - 1, k) + k - 1) % n + 1

# Driver function
if __name__ == "__main__":
    n, k = map(int, input("Enter values for n and k: ").split())
    print("The safe position is", josephus(n, k))
You can also try this code with Online Python Compiler
Run Code

Input-

6 3


Output-


Enter values for n and k.
6 3
The safe position is 1

 

Complexity Analysis

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

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

Frequently Asked Questions

How do you solve the Josephus Problem?

In programming, we solve Josephus's problem using recursion. We recursively delete the number at the kth position from the start. And keep track of the shift in starting position, thus finding the safe position.

What is the formula for the Josephus problem?

The formula is f(N,k)=(f(N−1,k)+k−1)modN+1, representing the safe position in a circle of N people after every k-th person is eliminated.

What is the binary solution of the Josephus problem?

The binary solution employs bitwise operations, providing an efficient way to find the safe position using the binary representation of the problem parameters.

Conclusion

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.
     

Recommended Articles

Also practice some of the questions mentioned below based on linkedlist data structure.

To read more about the recursion or linked list, visit these links- Recursion Linked list. You can also solve problems related to these on Coding Ninjas Studio. If you liked this blog, share it with your friends!

Live masterclass
author
System Design Questions Asked at Microsoft, Oracle, PayPal
by Pranav Malik
23 Apr, 2025
01:30 PM
discord 24+ registered
author
Master DSA to Ace MAANG SDE Interviews
by Saurav Prateek
21 Apr, 2025
01:30 PM
discord 474+ registered
author
Google Data Analyst roadmap: Essential SQL concepts
by Maaheen Jaiswal
22 Apr, 2025
01:30 PM
discord 1023+ registered
author
Amazon Data Analyst: Advanced Excel & AI Interview Tips
by Megna Roy
24 Apr, 2025
01:30 PM
discord 175+ registered
author
System Design Questions Asked at Microsoft, Oracle, PayPal
by Pranav Malik
23 Apr, 2025
01:30 PM
discord 24+ registered
author
Master DSA to Ace MAANG SDE Interviews
by Saurav Prateek
21 Apr, 2025
01:30 PM
discord 474+ registered
View more events