Josephus

Question:There are N people standing in a circle waiting to be executed. The counting out begins at some 
point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number 
of people are skipped and the next person is executed. The elimination proceeds around the circle 
(which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. 

Given the total number of persons N and a number k which indicates that k-1 persons are skipped and the kth person is killed in a circle.
The task is to choose the person in the initial circle that survives.


Example:Input: N = 5 and k = 2
Output: 3
Explanation: Firstly, the person at position 2 is killed, 
then the person at position 4 is killed, then the person at position 1 is killed. 
Finally, the person at position 5 is killed. So the person at position 3 survives. 


Input: N = 7 and k = 3
Output: 4
Explanations: The persons at positions 3, 6, 2, 7, 5, and 1 are killed in order, 
and the person at position 4 survives.


Code in Python Language:

def Josh(person, k, index):

  # Base case , when only one person is left
  if len(person) == 1:
    print(person[0])
    return

  # find the index of first person which will die
  index = ((index+k)%len(person))

   # remove the first person which is going to be killed
  person.pop(index)

  # recursive call for n-1 persons
  Josh(person,k,index)

# Driver Program to test above function
n = 14 # specific n and k  values for original josephus problem
k = 2
k-=1   # (k-1)th person will be killed

index = 0 

# fill the person vector
person=[]
for i in range(1,n+1):
  person.append(i)

Josh(person,k,index)



CODE IN C++

#include <bits/stdc++.h>

using namespace std;

void Josh(vector<int> person, int k, int index)
{
    // Base case , when only one person is left
    if (person.size() == 1) {
        cout << person[0] << endl;
        return;
    }

    // find the index of first person which will die
    index = ((index + k) % person.size());

    // remove the first person which is going to be killed
    person.erase(person.begin() + index);

    // recursive call for n-1 persons
    Josh(person, k, index);
}

int main()
{
    int n = 14; // specific n and k  values for original
                // josephus problem
    int k = 2;
    k--; // (k-1)th person will be killed
    int index
        = 0; // The index where the person which will die

    vector<int> person;
    // fill the person vector
    for (int i = 1; i <= n; i++) {
        person.push_back(i);
    }

    Josh(person, k, index);
}