# eliminate very kth element in mod n… save a given element for last

We are given $1,\ldots,n$ numbers. Let's say we are to save a given number element $k$ for last in elimination. We start eliminating them in the following manner. I eliminate $1$ at first. Then eliminate the next $k$th element (index $k+1$). And then keep doing the same wrapping around $n$ if needed. The numbers eliminated before don't count for elimination for counting till $k$, next time onwards. I want to find such $k$ that element given element no (say $i$) goes last in the elimination.

As sample: lets take 1 2 3 4 5 as input

Now say I want to save 5 for last. Thus min number $k=3$ in this case (ans).

Lets simulate it.
1 is eliminated first
4 goes next
3 goes next
2 goes next
and 5 is saved for last.

I need to find this minimum $(k=3)$ given $n$ and number i to save for last.

-
This is the Josephus problem. –  joriki Feb 13 '13 at 11:21