Josephus Problem: N people K Executions in Cycle

Problem:

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.

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.

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. 

Solution:

#include <bits/stdc++.h>
 
using namespace std;
 
void Solve(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
    Solve(person, k, index);
}
 
int main()
{
    int n = 7; 
    int k = 3;
    k--; 
    int index= 0; 
 
    vector<int> person;
    for (int i = 1; i <= n; i++) {
        person.push_back(i);
    }
 
    Solve(person, k, index);
}

// Time Complexity: O(n^2)
// Space Complexity: O(n) for using recursion

Optimized Solution:

#include <iostream>


int josephus(int n, int k) {
    int survivor = 0;

    // Calculate the position of the survivor iteratively
    for (int i = 2; i <= n; ++i) {
        survivor = (survivor + k) % i;
    }

    // The survivor is in 0-based index, so add 1 to get the 1-based index
    return survivor + 1;
}

int main() {
    int N1 = 5, k1 = 2;
    int N2 = 7, k2 = 3;

    int result1 = josephus(N1, k1);
    std::cout << "Survivor for Example 1: " << result1 << std::endl; // Output: 3
  
    int result2 = josephus(N2, k2);
    std::cout << "Survivor for Example 2: " << result2 << std::endl; // Output: 4

    return 0;
}
// Time Complexity: O(n)
// Space Complexity: O(1) 

Here’s an example to illustrate the logic:

• Suppose n = 5 and k = 2.
• Iteration 1: (survivor + k) % 2 -> (0 + 2) % 2 -> 0.
• Iteration 2: (survivor + k) % 3 -> (0 + 2) % 3 -> 2.
• Iteration 3: (survivor + k) % 4 -> (2 + 2) % 4 -> 0.
• Iteration 4: (survivor + k) % 5 -> (0 + 2) % 5 -> 2.
• Iteration 5: (survivor + k) % 6 -> (2 + 2) % 6 -> 4.

So, in this example, the survivor’s position is 4.