2

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.

Daniel W. Farlow
  • 22,531
Fluvid
  • 201
  • 2
    This is the Josephus problem. – joriki Feb 13 '13 at 11:21
  • 1
    Discussed at http://math.stackexchange.com/questions/126194/stepping-through-the-josephus-problem and http://math.stackexchange.com/questions/126895/josephus-problem-who-would-be-the-3rd-person-to-be-eliminated-for-a-circle-8 and http://math.stackexchange.com/questions/119010/josephus-puzzle-basic-java-with-some-basic-math and http://math.stackexchange.com/questions/147055/permutation-of-counting-out and probably half-a-dozen other places on this website. – Gerry Myerson Feb 13 '13 at 12:14

0 Answers0