algorithm - Take every k-th element from the (1 .. n) natural numbers series

Question

For example, we have series 1, 2, 3, 4, 5. We take every 3 element => 3, 1, 5, 2, 4 (chosen element shouldn't remain, we can take while series is not empty). Naive implementation by circle doubly linked list is not good idea cause of performance. Can you give me an advice which data structures and algorithms are more applicable?

Answer 1

If you just need the last number, it's known as Josephus problem and there're well-known formulas for computing the answer in O(N) time.

I don't know if one can adapt it to run a full simulation, so I'll describe a straightforward O(N log N) solution here:

Let's keep all numbers in a treap with implicit keys. We need to find the k-th element and delete it at each step (in fact, there can be a shift, so it's more like (cur_shift + k) % cur_size, but it doesn't really matter). A treap can do it. We just need to split it into 3 parts [0, k - 1], [k, k] and [k + 1, cur_size - 1], print the number in the node that corresponds to the second part and merge the first and last part back together. It requires O(log N) time per step, so it should be good enough for the given constraints.