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

Answer 2

You can build segment tree that can solve these type of operations

• M(p, v): Modify a[p] := v
• S(l, r): Calculate a[l] + a[l+1] + ... + a[r]
• F(p, k): Find min(x) that (x >= p) and S(1, x) >= k

All of above operations can be done in O(log n) time

Using the algorithm described above you can achieve same result in O(n log n)

/*
    @Author: SPyofgame
    @License: Free to use
*/

#include <iostream>
#include <vector>

using namespace std;

/// Segment Tree Data Structure
struct Segtree
{
    int n;
    vector<int> t;

    /// O(n)
    /// Construct Segment Tree
    void init(int lim)
    {
        for (n = 1; n < lim; n <<= 1);
        t.assign(n << 1, 0);
    }

    /// O(log n)
    /// Modify: a[pos] := v
    void modify(int pos, int v, int ct, int lt, int rt)
    {
        if (rt - lt == 1)
        {
            t[ct] = v;
            return ;
        }

        int mt = (lt + rt) >> 1;
        if (mt > pos)
            modify(pos, v, ct * 2 + 1, lt, mt);
        else 
            modify(pos, v, ct * 2 + 2, mt, rt);

        t[ct] = t[ct * 2 + 1] + t[ct * 2 + 2];
    }

    /// O(log n)
    void modify(int pos, int v)
    {
        return modify(pos, v, 0, 0, n);
    }
    
    /// O(log n)
    /// Query: Sigma(a[i] | l <= i <= r)
    int query(int l, int r, int ct, int lt, int rt)
    {
        if (lt >= r || l >= rt) return 0;
        if (lt >= l && r >= rt) return t[ct];

        int mt = (lt + rt) >> 1;
        int lv = query(l, r, ct * 2 + 1, lt, mt);
        int rv = query(l, r, ct * 2 + 2, mt, rt);
        return lv + rv;
    }

    /// O(log n)
    int query(int l, int r)
    {
        return query(l, r + 1, 0, 0, n);
    }

    /// O(log n)
    /// Search: Min(x | Query(1, x) >= k)
    int search_for(int k, int ct, int lt, int rt)
    {
        if (k > t[ct]) return -1;
        if (rt - lt == 1) return lt;

        int mt = (lt + rt) >> 1;
        int v = t[ct * 2 + 1];
        int res = search_for(k - 0, ct * 2 + 1, lt, mt);
        if (res == -1)
            res = search_for(k - v, ct * 2 + 2, mt, rt);
    
        return res;
    }

    /// O(log n)
    int search_for(int k)
    {
        return search_for(k, 0, 0, n);
    }

    /// O(log n)
    /// Search: Min(x | x >= pos & Query(1, x) >= k)
    int search_for_at_least(int pos, int k)
    {
        return search_for(k + query(1, pos - 1), 0, 0, n);
    }
};

int main()
{
    // file("Test");
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    /// Input: Number of element and steps
    int n, k;
    cin >> n >> k;

    Segtree T;
    T.init(n + 1);
    for (int x = 1; x <= n; ++x) /// O(n log n)
        T.modify(x, 1);

    int pos = 1;
    for (int remain = n; remain >= 1; --remain) /// O(n log n)
    {
        /// Number of steps
        int step = k + 1;
        
        /// Move move (remain) times remain the same pos
        step %= remain;
        if (step == 0) step = remain; /// Current pos my not the result, therefore move more (remain) steps

        /// The current segment is not the part we need to search
        int right = T.query(pos, n);
        if (step > right)
        {
            pos = 1; /// Set it back to first pos
            step -= right; /// Number of step traveled
        }

        /// Search for real pos
        pos = T.search_for_at_least(pos, step);
        T.modify(pos, 0);
        cout << pos << " ";
    }

    return 0;
}

You can also use Iterative Segment Tree

/*
    @Author: SPyofgame
    @License: Free to use
*/

#include <iostream>
 
using namespace std;
 
const int N = 1 << 18;
int T[N+N];

void init(int n)
{
    for (int i = 0; i < n; ++i) T[i + N] = 1;
    for (int i = N - 1; i > 0; --i) T[i] = T[i << 1] + T[i << 1 | 1];
}
 
int lower_bound(int x, int p = 1)
{
    while (p < N) if (T[p <<= 1] < x) x -= T[p++];
    return p - N;
}
 
void update(int p, int v)
{
    for (T[p += N] = v; p > 1; p >>= 1) T[p >> 1] = T[p] + T[p ^ 1];
}
 
int main()
{
    int n, k;
    cin >> n >> k;
    
    init(n);
    for (int remain = n, pos = 0; remain > 0; --remain)
    {
        pos += remain + k;
        pos %= remain;
        int p = lower_bound(pos + 1);
        cout << p + 1 << " ";
        update(p, 0);
    }
 
    return 0;
}