Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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); }

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(); } }

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)

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.

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

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

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.

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

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

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.

Algorithm

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.

Run a while loop from start = 0 to start< size of array(N):

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

Increment end by 1 and then perform modulo N in the next step.

If arr[end] = 1, add one to size by 1.

Set size = 1, arr[end] = 0, and increment start and end by one and end = end % N.

Run a while loop till arr[end] = 0 and increment end by one.

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

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)); } }

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

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(N^{2}).

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

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

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(); } }

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

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.

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.

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

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(); } }

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

Input-

6 3

Output-

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

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

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(); } }

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

Input-

6 3

Output-

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

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.

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