Josephus Permutation (Removal Order) in O(n.logn)

Question

Is there a way to print out the order of removal in the Josephus problem in O(n.logn) ?

Example

With number of people is n = 7 and number of skip k = 3. The order of elimination would be:

3, 6, 2, 7, 5, 1, 4

Answer 1

There's an approach that uses ordered set

(https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/):

• Initialize an ordered set V, and insert the elements in the range [1, N] into V.
• Initialize a variable, say pos as 0, to store the index of the removed element.
• Iterate until the size of V is greater than 1, and perform the following steps:
  • Store the size of the set in a variable, say X
  • Update the value of pos to (pos + K) % X
  • Print the element pointed by pos in V and then erase it
  • Update pos to pos%V.size()
• Print the last element stored at the beginning of set V

Here's the code:

#include <iostream>
using namespace std;

// Header files, namespaces to use
// ordered set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set                          \
    tree<int, null_type, less<int>, rb_tree_tag, \
        tree_order_statistics_node_update>

// Function to find the person who
// will get killed in the i'th step
void orderOfExecution(int N, int K)
{

    // Create an ordered set
    ordered_set V;

    // Push elements in the range
    // [1, N] in the set
    for (int i = 1; i <= N; ++i)
        V.insert(i);

    // Stores the position to be removed
    int pos = 0;

    // Iterate until the size of the set
    // is greater than 1
    while (V.size() > 1) {

        // Update the position
        pos = (pos + K) % (int)V.size();

        // Print the removed element
        cout << *(V.find_by_order(pos)) << ' ';

        // Erase it from the ordered set
        V.erase(*(V.find_by_order(pos)));

        // Update position
        pos %= (int)V.size();
    }

    // Print the first element of the set
    cout << *(V.find_by_order(0));
}

int main()
{
    int N = 5, K = 2;

    // Function Call
    orderOfExecution(N, K);

    return 0;
}

Time Complexity: O(N * log(N))

For better understanding, I recommend checking out this video:

https://youtu.be/KnsDFCcBJbY