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:
-
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.
-
Test Case 2: n = 31, k = 4
With 31 people and counting every 4th person, the survivor will be in position 10.
-
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:
- 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. - Otherwise, the function calls itself recursively with
num - 1
(the remaining number of people) andk
(the step size to skip). The result of the recursive call represents the position of the survivor in the reduced circle ofnum - 1
people. - The algorithm then adds
k - 1
to the result of the recursive call, as this represents the number of steps to skip the nextk-th
person. - 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 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;
}
input
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);
}
}
input
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;
}
input
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);
}
}
input
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();
input
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();
input
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()
input
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()
input
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);
}
}
input
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();
input
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);
}
input
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:
- For
n = 23
andk = 8
, the survivor is in position 2. - For
n = 31
andk = 4
, the survivor is in position 10. - For
n = 34
andk = 2
, the survivor is in position 5.
The algorithm efficiently solves the Josephus problem using recursion and provides accurate results for the given inputs.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment