Josephus Problem

I decided to give this one a try. I knew that there exists an algorithm to solve this problem but it is more fun to try, fail, then try once more, fail again and then pounce on the known algorithm when the suspense becomes unbearable !:D

The simplest idea that comes to mind is to create a circular singly-linked list from the numbers and go on deleting the nodes, which is quite a violent activity actually, since it is equivalent to killing the people in the circle !!:D. So the next time you decide to delete a node, think twice :P

Anyways, this algorithm though quite simple is probably overkill for the problem and involves linked list manipulations. Equivalently, an array may be used as well, where the killed soldiers are marked by a special entry in the array.

Then, I had a glance at the algorithm and noticed that it doesnt use arrays or linked lists. I decided to give this approach a try.

But the question was what to track ? Do I track the last number that was deleted or the last number remaining after a round of deleting numbers from the array ?

(more coming soon ... )