Josephus Problem II

Consider a game where there are n$n$ children (numbered 1,2,…,n) in a circle. During the game, repeatedly k children are skipped and one child is removed from the circle. In which order will the children be removed?

Example:

Input:  n = 7 , k = 2
Output: 3 6 2 7 5 1 4 

Approach

C++

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class K, class V>
using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

vector<int> josephusProblemII(int n, int k)
{

    vector<int> a(n);

    vector<int> res;
    iota(a.begin(), a.end(), 1);
    ordered_set<int> os(a.begin(), a.end());
    int pos = 0;
    while (os.size())
    {
        pos = (pos + k) % (os.size());
        res.push_back(*os.find_by_order(pos));
        os.erase(os.find_by_order(pos));
    }
    return res;
}

int main()
{
    int n = 7, k = 2;

    vector<int> res = josephusProblemII(n, k);

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

    return 0;
}