Can my algorithm be done any better?

Question

I have been presented with a challenge to make the most effective algorithm that I can for a task. Right now I came to the complexity of n * logn. And I was wondering if it is even possible to do it better. So basically the task is there are kids having a counting out game. You are given the number n which is the number of kids and m which how many times you skip someone before you execute. You need to return a list which gives the execution order. I tried to do it like this you use skip list.

Current = m
while table.size>0:
    executed.add(table[current%table.size])
    table.remove(current%table.size)
    Current += m

My questions are is this correct? Is it n*logn and can you do it better?

You ask if it is correct, so I ask: well, have you tried to implement it? It shouldn't take you a lot of time to implement it and see for yourself if you get the expected output. Also if you want people to tell you how you can improve your code, I would point you to http://codereview.stackexchange.com/. — PJvG, Apr 12 '17 at 08:33
@n.m. : It is not the *Josephus problem* as defined in https://en.wikipedia.org/wiki/Josephus_problem because knowing who wins is different from generating the list of the execution order. — MrSmith42, Apr 12 '17 at 08:37

score 3 · Answer 1 · edited May 23 '17 at 10:30

Is this correct?

No. When you remove an element from the table, the table.size decreases, and current % table.size expression generally ends up pointing at another irrelevant element. For example, 44 % 11 is 0 but 44 % 10 is 4, an element in a totally different place.

Is it n*logn?

No. If table is just a random-access array, it can take n operations to remove an element. For example, if m = 1, the program, after fixing the point above, would always remove the first element of the array. When an array implementation is naive enough, it takes table.size operations to relocate the array each time, leading to a total to about n^2 / 2 operations in total.

Now, it would be n log n if table was backed up, for example, by a balanced binary search tree with implicit indexes instead of keys, as well as split and merge primitives. That's a treap for example, here is what results from a quick search for an English source. Such a data structure could be used as an array with O(log n) costs for access, merge and split. But nothing so far suggests this is the case, and there is no such data structure in most languages' standard libraries.

Can you do it better?

Correction: partially, yes; fully, maybe.

If we solve the problem backwards, we have the following sub-problem.

Let there be a circle of k kids, and the pointer is currently at kid t. We know that, just a moment ago, there was a circle of k + 1 kids, but we don't know where, at which kid x, the pointer was. Then we counted to m, removed the kid, and the pointer ended up at t. Whom did we just remove, and what is x?

Turns out the "what is x" part can be solved in O(1) (drawing can be helpful here), so the finding the last kid standing is doable in O(n). As pointed out in the comments, the whole thing is called Josephus Problem, and its variants are studied extensively, e.g., in Concrete Mathematics by Knuth et al.

However, in O(1) per step, this only finds the number of the last standing kid. It does not automatically give the whole order of counting the kids out. There certainly are ways to make it O(log(n)) per step, O(n log(n)) in total. But as for O(1), I don't know at the moment.

Thanks a lot we'll I have been looking at the josephus problem but did not come to the simple solution as to add and reverse. We'll go adress your first point I could just fix that by setting m up before I remove an element so the pointer to the element would stay correct and than add m. For the remove I assumed to have a skip list :) — Jani, Apr 12 '17 at 09:34
The only problem I see if I use josefus I still need to keep track somehow what I removed since it only gives me the position let's say number 3 was removed first round now again number 3 comes up but it is removed so 4 is removed — Jani, Apr 12 '17 at 09:41

MrSmith42 · Answer 2 · 2017-04-12T08:50:37.293

1

Complexity of your algorithm depends on the complexity of the operations executed.add(..) and table.remove(..).

If both of them have complexity of O(1), your algorithm has complexity of O(n) because the loop terminates after n steps.

While executed.add(..) can easily be implemented in O(1), table.remove(..) needs a bit more thinking.

You can make it in O(n):

Store your persons in a LinkedList and connect the last element with the first. Removing an element costs O(1). Goging to the next person to choose would cost O(m) but that is a constant = O(1).

This way the algorithm has the complexity of O(n*m) = O(n) (for constant m).

edited Apr 12 '17 at 08:50

answered Apr 12 '17 at 08:33

MrSmith42

9,961
6
38
49

It is strange to suggest getting rid of `m` in the complexity. If `n` is large (and even if not), nothing in the problem setting prevents `m` to be, e.g., larger than `n`. – Gassa Apr 12 '17 at 09:31
@Gassa: It's not about the size of m. The **O notations** refers to asymtotic behavior. So it depends on how you define your input. If m is a constant it does not matter how big it is it adds nothing to the complexity described by the **O notation** . – MrSmith42 Apr 12 '17 at 10:00
@MrSmith42 OK, in these terms, it is not feasible for this problem to define the input as {n} and not {n, m}. – Gassa Apr 12 '17 at 10:30

Can my algorithm be done any better?

2 Answers2