Josephus Problem I

Consider a game where there are n children (numbers from 1,2,3,....,n) in a circle. During the game, every second child is removed from the circle, until there are no children left. In which order will the children be removed?

Example:

Input:  7
Output: 2 4 6 1 5 3 7 

Approach

C++

#include <bits/stdc++.h>
using namespace std;

//function to solve the josephus problem
vector<int> josephusProblemI(int n)
{
    list<int> arr;
    for (int i = 1; i <= n; i++)
    {
        arr.push_back(i);
    }
    auto it = arr.begin();

    //vector array to store the result
    vector<int> res;
    while (arr.size() > 0)
    {
        it++;
        if (it == arr.end())
            it = arr.begin();
        res.push_back(*it);
        it = arr.erase(it);
        if (it == arr.end())
            it = arr.begin();
    }
    return res;
}
int main()
{

    int n = 7;

    vector<int> res = josephusProblemI(n);

    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    return 0;
}