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

Build a complete binary tree containing the numbers 1 to n, e.g. for n=15 that would be:

In each branch, store the number of nodes to the left of it; this will allow us to quickly find the i-th node. (You'll see that this tree has a very predictable structure and values, and generating it is much more efficient than building a same-sized binary tree with randomly-ordered values. It's also an ideal candidate for a tree-in-an-array.)

Then, to find the i-th number, start at the root node, and at every node, if i is one greater than the number of nodes to the left, you've found the i-th number, else go left (if i is not greater than the number of nodes to the left) or right (if i is more than 1 greater than the number of nodes to the left).

Whenever you go left, decrement the count of nodes to the left of this node (because we'll be removing one).

Whenever you go right, decrease the number you're looking for by the number of nodes to the left of the node, plus 1 (or plus 0 if the value in the node has been erased).

When you've found the i-th node, read its value (to add to the removal order list) and then set its value to 0. Thereafter, if the i-th node we're looking for has had its value erased, we'll go right and then take the leftmost node.

We start with a value i = k, and then every time we've erased the number in the i-th node, we'll decrement the total number of nodes and set i = (i + k - 1) % total (or if that is zero: i = total).

This gives a log₂N lookup time and a total complexity of N×LogN.

---

Example walk-through: with n=15 (as in the image above) and k=6, the first steps are 6, 12, 3, 10, 2. At that point the situation is:

We've just removed the second number, and now i = 2 + 6 - 1 = 7. We start at the root node, which has 4 nodes to the left of it and still has its value, so we go right and subtract 5 from the 7 we're looking for and get 2. We arrive at node 12 (which has been erased) and find there are 2 nodes to the left of it, so we decrement the number of nodes to the left of it and then go left. We come to node 10 (which has been erased) and find that it has 1 node to the left of it, and 1 = 2 - 1 so this is the node we're looking for; however, since its value has been erased, we go right and subtract 1 from the 2 we're looking for and get 1. We arrive at node 11, which has 0 nodes to the left of it (because it's a leaf), and 0 = 1 - 1, so this is the node we're looking for.

We then decrement the total number of nodes from 10 to 9, and update i from 7 to (7 + 6 - 1) % 9 = 3 and go on to find the third node (which is now the one with value 5).

---

Here's a simple implementation in JavaScript. It solves series of 100,000 numbers in less than a second, and it could probably be made faster and more space-efficient by using a tree-in-an-array structure.

(Unlike in the explanation above, the indexes of the numbers are zero-based, to simplify the code; so index 0 is the first number in the tree, and we look for the node with a number of left-connected children that equals the target index.)

function Tree(size) {                      // CONSTRUCTOR
    var height = Math.floor(Math.log(size) / Math.log(2));
    this.root = addNode(height, 1 << height, size);
    this.size = size;
    function addNode(height, value, max) { // RECURSIVE TREE-BUILDER
        var node = {value: value > max ? 0 : value, lower: (1 << height) - 1};
        if (height--) {
            node.left = addNode(height, value - (1 << height), max);
            if (value < max) {             // DON'T ADD UNNECESSARY RIGHT NODES
                node.right = addNode(height, value + (1 << height), max);
            }
        }
        return node;
    }
}
Tree.prototype.cut = function(step) {      // SEE ANSWER FOR DETAILS
    var sequence = [], index = (step - 1) % this.size;
    while (this.size) {
        var node = this.root, target = index;
        while (node.lower != target || node.value == 0) {
            if (target < node.lower) {
                --node.lower;
                node = node.left;
            } else {
                target -= node.lower + (node.value ? 1 : 0);
                node = node.right;
            }
        }
        sequence.push(node.value);
        node.value = 0;
        index = (index + step - 1) % --this.size;
    }
    return sequence;
}
var tree = new Tree(15);
var sequence = tree.cut(6);
document.write("15/6&rarr;" + sequence + "<BR>");

tree = new Tree(100000);
sequence = tree.cut(123456);
document.write("100000/123456&rarr;" + sequence);

---

NOTE:

If you look at the tree for n=10, you'll see that the node to the right of the root has an incomplete tree with 2 nodes to its left, but the algorithm as implemented in the code example above gives it an incorrect left-node count of 3 instead of 2:

However, nodes with an incomplete tree to their left never hold a value themselves, and never have nodes to their right. So you always go left there anyway, and the fact that their left-node count is too high is of no consequence.

Answer 2

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.