Josephus Problem II

Josephus Problem II
CSES medium

There are \(n\) children in a circle, numbered \(1, 2, \ldots, n\). Repeatedly, \(k\) children are skipped and the next child is removed from the circle.

In which order are the children removed?

Constraints:

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(0 \le k \le 10^9\)

Input:

  • One line: two integers \(n\) and \(k\).

Output:

  • \(n\) integers — the removal order.

Example:

Input:

7 2

Output:

3 6 2 7 5 1 4
Solution

We keep the children who are still in the circle in an ordered_set, and pos, the index (from \(0\)) of the child where counting starts. At the start, pos is \(0\).

In each round, we skip \(k\) children, so the removed child has index \((pos + k) \bmod size\), where \(size\) is the number of children left. find_by_order finds this child in \(O(\log n)\), and we erase it.

After the removal, the child that followed the removed one moves into the same index, so the next round starts counting from pos again. If the removed child was the last one in the order, the next round starts from index \(0\); the modulo in the next round handles this.

For the example (\(k = 2\)): from 1 2 3 4 5 6 7 we remove index \(2\) (child \(3\)), then from 1 2 4 5 6 7 index \(4\) (child \(6\)), then from 1 2 4 5 7 index \(6 \bmod 5 = 1\) (child \(2\)), and so on.

The time complexity is \(O(n \log n)\).

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long k;
    cin >> n >> k;

    ordered_set<int> children;
    for (int i = 1; i <= n; i++) {
        children.insert(i);
    }

    int pos = 0;  // index of the child where counting starts
    while (!children.empty()) {
        pos = (pos + k) % children.size();
        auto it = children.find_by_order(pos);
        cout << *it << ' ';
        children.erase(it);
        // the next child moves into index pos
    }
    cout << "\n";
}