Josephus problem using recursion

The Josephus problem is a famous theoretical problem in mathematics and computer science. It is named after the Jewish historian Flavius Josephus, who, according to the legend, found a way to avoid execution during a siege by the Romans. The problem can be stated as follows:

Suppose there are n people standing in a circle, numbered from 1 to n. Starting from person 1, you begin counting in a fixed direction (either clockwise or counterclockwise) and skip k-1 people. The k-th person is then removed from the circle. The process is repeated with the remaining n-1 people until only one person remains, who is declared the survivor.

The task is to find the position of the survivor given the values of n (the number of people) and k (the step size to skip).

Explanation using Example

Let's consider the test cases from the provided code:

1. Test Case 1: n = 23, k = 8

   In this case, with 23 people and counting every 8th person, the survivor will be in position 2.

2. Test Case 2: n = 31, k = 4

   With 31 people and counting every 4th person, the survivor will be in position 10.

3. Test Case 3: n = 34, k = 2

   With 34 people and counting every 2nd person, the survivor will be in position 5.

Pseudocode

josephusSolution(num, k)
    if num is 1
        return 1
    return (josephusSolution(num - 1, k) + k - 1) % num + 1

josephus(num, k)
    if num <= 0 or k <= 0
        return
    result = josephusSolution(num, k)
    print "Number : num  K : k"
    print "Result : result"

Algorithm Explanation

The josephusSolution function is a recursive algorithm to find the position of the survivor in the Josephus problem. It takes two parameters: num (the number of people in the circle) and k (the step size to skip). The algorithm calculates the position of the survivor recursively using the following steps:

1. If num is equal to 1, it means there is only one person remaining, and they are the survivor. In this case, the function returns 1.
2. Otherwise, the function calls itself recursively with num - 1 (the remaining number of people) and k (the step size to skip). The result of the recursive call represents the position of the survivor in the reduced circle of num - 1 people.
3. The algorithm then adds k - 1 to the result of the recursive call, as this represents the number of steps to skip the next k-th person.
4. Finally, the algorithm takes the result modulo num to wrap around the circle and adds 1 to account for the 1-based indexing.

The josephus function handles the request to find the survivor position for a given num and k. It first checks if the inputs num and k are valid (greater than 0). If either of them is not valid, the function returns without further processing. Otherwise, it calls the josephusSolution function to calculate the position of the survivor and prints the given information and the calculated result.

Program Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// C program for 
// Josephus problem using recursion
#include <stdio.h>

int josephusSolution(int num, int k)
{
	if (num == 1)
	{
		// Stop recursion process
		return 1;
	}
	// Recursively finding the solution
	return (josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
void josephus(int num, int k)
{
	if (num <= 0 || k <= 0)
	{
		// Invalid inputs
		return;
	}
	int result = josephusSolution(num, k);
	// Display given info
	printf(" Number : %d  K : %d\n", num, k);
	// Display calculated result
	printf(" Result : %d \n", result);
}
int main(int argc, char
	const *argv[])
{
	// Test Case
	josephus(23, 8);
	josephus(31, 4);
	josephus(34, 2);
	return 0;
}

 Number : 23  K : 8
 Result : 2
 Number : 31  K : 4
 Result : 10
 Number : 34  K : 2
 Result : 5

/*
  Java Program for
  Josephus problem using recursion
*/
public class Calculation
{
	public int josephusSolution(int num, int k)
	{
		if (num == 1)
		{
			// Stop recursion process
			return 1;
		}
		// Recursively finding the solution
		return (josephusSolution(num - 1, k) + k - 1) % num + 1;
	}
	// Handles the request of finding josephus solution
	public void josephus(int num, int k)
	{
		if (num <= 0 || k <= 0)
		{
			// Invalid inputs
			return;
		}
		int result = josephusSolution(num, k);
		// Display given info
		System.out.println(" Number : " + num + " K : " + k);
		// Display calculated result
		System.out.println(" Result : " + result);
	}
	public static void main(String[] args)
	{
		Calculation task = new Calculation();
		// Test Case
		task.josephus(23, 8);
		task.josephus(31, 4);
		task.josephus(34, 2);
	}
}

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5

// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  Josephus problem using recursion
*/
class Calculation
{
	public: int josephusSolution(int num, int k)
	{
		if (num == 1)
		{
			// Stop recursion process
			return 1;
		}
		// Recursively finding the solution
		return (this->josephusSolution(num - 1, k) + k - 1) % num + 1;
	}
	// Handles the request of finding josephus solution
	void josephus(int num, int k)
	{
		if (num <= 0 || k <= 0)
		{
			// Invalid inputs
			return;
		}
		int result = this->josephusSolution(num, k);
		// Display given info
		cout << " Number : " << num << " K : " << k << endl;
		// Display calculated result
		cout << " Result : " << result << endl;
	}
};
int main()
{
	Calculation *task = new Calculation();
	// Test Case
	task->josephus(23, 8);
	task->josephus(31, 4);
	task->josephus(34, 2);
	return 0;
}

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5

// Include namespace system
using System;
/*
  Csharp Program for
  Josephus problem using recursion
*/
public class Calculation
{
	public int josephusSolution(int num, int k)
	{
		if (num == 1)
		{
			// Stop recursion process
			return 1;
		}
		// Recursively finding the solution
		return (this.josephusSolution(num - 1, k) + k - 1) % num + 1;
	}
	// Handles the request of finding josephus solution
	public void josephus(int num, int k)
	{
		if (num <= 0 || k <= 0)
		{
			// Invalid inputs
			return;
		}
		int result = this.josephusSolution(num, k);
		// Display given info
		Console.WriteLine(" Number : " + num + " K : " + k);
		// Display calculated result
		Console.WriteLine(" Result : " + result);
	}
	public static void Main(String[] args)
	{
		Calculation task = new Calculation();
		// Test Case
		task.josephus(23, 8);
		task.josephus(31, 4);
		task.josephus(34, 2);
	}
}

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5

<?php
/*
  Php Program for
  Josephus problem using recursion
*/
class Calculation
{
	public	function josephusSolution($num, $k)
	{
		if ($num == 1)
		{
			// Stop recursion process
			return 1;
		}
		// Recursively finding the solution
		return ($this->josephusSolution($num - 1, $k) + $k - 1) % $num + 1;
	}
	// Handles the request of finding josephus solution
	public	function josephus($num, $k)
	{
		if ($num <= 0 || $k <= 0)
		{
			// Invalid inputs
			return;
		}
		$result = $this->josephusSolution($num, $k);
		// Display given info
		echo " Number : ".$num.
		" K : ".$k.
		"\n";
		// Display calculated result
		echo " Result : ".$result.
		"\n";
	}
}

function main()
{
	$task = new Calculation();
	// Test Case
	$task->josephus(23, 8);
	$task->josephus(31, 4);
	$task->josephus(34, 2);
}
main();

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5

/*
  Node JS Program for
  Josephus problem using recursion
*/
class Calculation
{
	josephusSolution(num, k)
	{
		if (num == 1)
		{
			// Stop recursion process
			return 1;
		}
		// Recursively finding the solution
		return (this.josephusSolution(num - 1, k) + k - 1) % num + 1;
	}
	// Handles the request of finding josephus solution
	josephus(num, k)
	{
		if (num <= 0 || k <= 0)
		{
			// Invalid inputs
			return;
		}
		var result = this.josephusSolution(num, k);
		// Display given info
		console.log(" Number : " + num + " K : " + k);
		// Display calculated result
		console.log(" Result : " + result);
	}
}

function main()
{
	var task = new Calculation();
	// Test Case
	task.josephus(23, 8);
	task.josephus(31, 4);
	task.josephus(34, 2);
}
main();

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5

#  Python 3 Program for
#  Josephus problem using recursion
class Calculation :
	def josephusSolution(self, num, k) :
		if (num == 1) :
			#  Stop recursion process
			return 1
		
		#  Recursively finding the solution
		return (self.josephusSolution(num - 1, k) + k - 1) % num + 1
	
	#  Handles the request of finding josephus solution
	def josephus(self, num, k) :
		if (num <= 0 or k <= 0) :
			#  Invalid inputs
			return
		
		result = self.josephusSolution(num, k)
		#  Display given info
		print(" Number : ", num ," K : ", k)
		#  Display calculated result
		print(" Result : ", result)
	

def main() :
	task = Calculation()
	#  Test Case
	task.josephus(23, 8)
	task.josephus(31, 4)
	task.josephus(34, 2)

if __name__ == "__main__": main()

 Number :  23  K :  8
 Result :  2
 Number :  31  K :  4
 Result :  10
 Number :  34  K :  2
 Result :  5

#  Ruby Program for
#  Josephus problem using recursion
class Calculation 
	def josephusSolution(num, k) 
		if (num == 1) 
			#  Stop recursion process
			return 1
		end

		#  Recursively finding the solution
		return (self.josephusSolution(num - 1, k) + k - 1) % num + 1
	end

	#  Handles the request of finding josephus solution
	def josephus(num, k) 
		if (num <= 0 || k <= 0) 
			#  Invalid inputs
			return
		end

		result = self.josephusSolution(num, k)
		#  Display given info
		print(" Number : ", num ," K : ", k, "\n")
		#  Display calculated result
		print(" Result : ", result, "\n")
	end

end

def main() 
	task = Calculation.new()
	#  Test Case
	task.josephus(23, 8)
	task.josephus(31, 4)
	task.josephus(34, 2)
end

main()

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5

/*
  Scala Program for
  Josephus problem using recursion
*/
class Calculation()
{
	def josephusSolution(num: Int, k: Int): Int = {
		if (num == 1)
		{
			// Stop recursion process
			return 1;
		}
		// Recursively finding the solution
		return (josephusSolution(num - 1, k) + k - 1) % num + 1;
	}
	// Handles the request of finding josephus solution
	def josephus(num: Int, k: Int): Unit = {
		if (num <= 0 || k <= 0)
		{
			// Invalid inputs
			return;
		}
		var result: Int = josephusSolution(num, k);
		// Display given info
		println(" Number : " + num + " K : " + k);
		// Display calculated result
		println(" Result : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Calculation = new Calculation();
		// Test Case
		task.josephus(23, 8);
		task.josephus(31, 4);
		task.josephus(34, 2);
	}
}

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5

/*
  Swift 4 Program for
  Josephus problem using recursion
*/
class Calculation
{
	func josephusSolution(_ num: Int, _ k: Int)->Int
	{
		if (num == 1)
		{
			// Stop recursion process
			return 1;
		}
		// Recursively finding the solution
		return (self.josephusSolution(num - 1, k) + k - 1) % num + 1;
	}
	// Handles the request of finding josephus solution
	func josephus(_ num: Int, _ k: Int)
	{
		if (num <= 0 || k <= 0)
		{
			// Invalid inputs
			return;
		}
		let result: Int = self.josephusSolution(num, k);
		// Display given info
		print(" Number : ", num ," K : ", k);
		// Display calculated result
		print(" Result : ", result);
	}
}
func main()
{
	let task: Calculation = Calculation();
	// Test Case
	task.josephus(23, 8);
	task.josephus(31, 4);
	task.josephus(34, 2);
}
main();

 Number :  23  K :  8
 Result :  2
 Number :  31  K :  4
 Result :  10
 Number :  34  K :  2
 Result :  5

/*
  Kotlin Program for
  Josephus problem using recursion
*/
class Calculation
{
	fun josephusSolution(num: Int, k: Int): Int
	{
		if (num == 1)
		{
			// Stop recursion process
			return 1;
		}
		// Recursively finding the solution
		return (this.josephusSolution(num - 1, k) + k - 1) % num + 1;
	}
	// Handles the request of finding josephus solution
	fun josephus(num: Int, k: Int): Unit
	{
		if (num <= 0 || k <= 0)
		{
			// Invalid inputs
			return;
		}
		val result: Int = this.josephusSolution(num, k);
		// Display given info
		println(" Number : " + num + " K : " + k);
		// Display calculated result
		println(" Result : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Calculation = Calculation();
	// Test Case
	task.josephus(23, 8);
	task.josephus(31, 4);
	task.josephus(34, 2);
}

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5

Time Complexity

The time complexity of the provided algorithm is O(n), where n is the number of people in the circle. This is because the algorithm needs to calculate the survivor position recursively, and each recursive call reduces the problem size by 1.

Resultant Output Explanation

The code correctly finds the position of the survivor for the given test cases:

1. For n = 23 and k = 8, the survivor is in position 2.
2. For n = 31 and k = 4, the survivor is in position 10.
3. For n = 34 and k = 2, the survivor is in position 5.

The algorithm efficiently solves the Josephus problem using recursion and provides accurate results for the given inputs.