CodeDAA.cpp

#include <iostream>
#include <vector>
using namespace std; // Function to solve the Josephus Problem
 
int josephus(int n, int k) 
{
    if (n == 1)
        return 0;
// Recursive step:
    int lastOne = (josephus(n - 1, k) + k) % n;
    return lastOne;
}
 
int lastPerson(int n, int k) 
{
    //  the result from the josephus function is 0 index, we add 1 based indexing
    return josephus(n, k) + 1;
}
 
int main() 
{
    int n, step;
    cout << "Enter the number of people in the circle: ";
    cin >> n;
 
    cout << "Enter the step size: ";
    cin >> step;
 
    //  using the decrease-and-conquer algorithm
    int lastOne = lastPerson(n, step);
    cout << "The last person standing is at position: " << lastOne << endl;
    return 0;
}