CODEWITHSUNDEEP
algorithmdata-structuresjosephus
user2045279
user2045279

Reputation: 711

The Josephus prob using a circular list in O(n)

I've recently stumbled upon a forum claiming that the Josephus problem can be solved in O(n) with a data structure. The clear choice here is a circular linked list, but I claim that it can only be done in O(kn) or O(n^2) unless you do the mathematical recursive/iterative josephus algorithm a la wikipedia. First things first, a circular linked list has the following properties: Search O(n), Delete O(1), Append O(1). This assumes delete is a given node and append is replacing the head or tail.

If we have a circular list of nodes, we can find the node to delete from the start point as follows:

n = 6 nodes

k = delete every 3rd node

StartingPoint: node #0

Nodes: 0, 1, 2, 3, 4, 5

We can calculate which node to delete via (k + StartingPoint - 1) % n. For startpoint = 0, we have (3 + 0 - 1) % 6 = 2. Now, 3 would be our starting point. (3 + 3 - 1) % 5 = 0, which when shifted is our original 5 node (ie. the numbers would now be 0,1,2,3,4 since original 2 is gone). That's basically how the mathematical version works. For a linked list, we can derive which node needs deleting similarly. The problem is that we have to travel to this node. Linked lists have O(n) search, which is a problem. So we traverse to this node, delete it, now we have n = n-1. We find the next index, do an O(n) search and have n = n_original - 2. This becomes n + (n-1) + (n-2) + ... = O(n^2).

If we have a doubly linked circular list, then we wouldn't have to go the whole way around if the node was closer from behind us. Still, this is O(k) search if k is smaller than n, and O(n) search if k is bigger than n (since you can only ever move n nodes before you get where you started, but if k is small, you only have to move k away and you wont reach where you started yet).

Regardless, my point is I don't see how you could do this via a data structure in O(n). The solution on wikipedia is a very elegant mathematical way in O(n) which shows the power of recursion (keeping track of old starting points purely by the call stack, etc.), but when deleting actual objects it seems impossible to get O(n). I wanted to display my attempts at figuring this out and not just blatantly ask, so does anyone know a way to do this in O(n) with some data structure? Thanks!

Upvotes: 2

Views: 3654

Answers (1)

user448810
user448810

Reputation: 17876

I solve this problem with a circular linked list in O(n) time at my blog. That web site also has an O(n) solution using a queue and an O(n^2) solution using a plain (not circular) linked list. With a circular linked list you always move forward, never backward, as you are suggesting with the doubly linked list.

As an example, look at your list. You start at 0, count 3, and delete item 3. Then count 3 and delete 0. Then count 3 and delete 4. Then count 3 and delete 2. Then count 3 and delete 5. Finally count 3 and delete 1. The total number of steps taken is kn, where n is the number of nodes and k is the step size. But this is O(n) in the number of nodes, since n is the problem size and k is a constant.

Upvotes: 1

Related Questions