# C++: Josephus Problem

Josephus problem is a math puzzle with a grim description: n prisoners are standing on a circle, sequentially numbered from 0 to n − 1.

An executioner walks along the circle, starting from prisoner 0, removing every k-th prisoner and killing him.

As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed.
For example, if there are n = 5 prisoners and k = 2, the order the prisoners are killed in (let’s call it the “killing sequence”) will be 1, 3, 0, and 4, and the survivor will be #2.

Task Given any n,k > 0, find out which prisoner will be the final survivor. In one such incident, there were 41 prisoners and every 3rd prisoner was being killed (k= 3). Among them was a clever chap name Josephus who worked out the problem, stood at the surviving position, and lived on to tell the tale. Which number was he?

```#include <iostream>
#include <vector>

//--------------------------------------------------------------------------------------------------
using namespace std;
typedef unsigned long long bigint;

//--------------------------------------------------------------------------------------------------
class josephus
{
public:
bigint findSurvivors( bigint n, bigint k, bigint s = 0 )
{
bigint i = s + 1;
for( bigint x = i; x <= n; x++, i++ )
s = ( s + k ) % i;

return s;
}

void getExecutionList( bigint n, bigint k, bigint s = 1 )
{
cout << endl << endl << "Execution list: " << endl;

prisoners.clear();
for( bigint x = 0; x < n; x++ )
prisoners.push_back( x );

bigint index = 0;
while( prisoners.size() > s )
{
index += k - 1;
if( index >= prisoners.size() ) index %= prisoners.size();
cout << prisoners[static_cast<unsigned int>( index )] << ", ";

vector<bigint>::iterator it = prisoners.begin() + static_cast<unsigned int>( index );
prisoners.erase( it );
}
}

private:
vector<bigint> prisoners;
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
josephus jo;
bigint n, k, s;
while( true )
{
system( "cls" );
cout << "Number of prisoners( 0 to QUIT ): "; cin >> n;
if( !n ) return 0;
cout << "Execution step: "; cin >> k;
cout << "How many survivors: "; cin >> s;

cout << endl << "Survivor";
if( s == 1 )
{
cout << ": " << jo.findSurvivors( n, k );
jo.getExecutionList( n, k );
}
else
{
cout << "s: ";
for( bigint x = 0; x < s; x++ )
cout << jo.findSurvivors( n, k, x ) << ", ";

jo.getExecutionList( n, k, s );
}

cout << endl << endl;
system( "pause" );
}
return 0;
}
//--------------------------------------------------------------------------------------------------
```
Output:
```Number of prisoners( 0 to QUIT ): 41
Execution step: 3
How many survivors: 1

Survivor: 30

Execution list:
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36
, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15,

Number of prisoners( 0 to QUIT ): 41
Execution step: 3
How many survivors: 3

Survivors: 30, 15, 34,

Execution list:
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36
, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3,

Number of prisoners( 0 to QUIT ): 71
Execution step: 47
How many survivors: 11

Survivors: 29, 58, 41, 14, 39, 28, 35, 45, 64, 49, 27,

Execution list:
46, 22, 70, 48, 26, 5, 56, 36, 17, 0, 54, 38, 23, 9, 66, 55, 43, 33, 25, 16, 11,
6, 2, 69, 68, 1, 4, 10, 15, 24, 32, 42, 53, 65, 20, 40, 60, 19, 47, 8, 44, 13,
52, 31, 12, 62, 57, 50, 51, 61, 7, 30, 59, 34, 18, 3, 21, 37, 67, 63,```

SOURCE

Content is available under GNU Free Documentation License 1.2.