Wednesday, April 16, 2014

How does the approach to solve Josephus problem work?

Josephus problem:
There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.
The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

The approach:

Lets say we have to find the solution for n=5 and k=3 (We kill every 3rd person)

Step 1: Kill the kth person (in our case, kill the 3rd person). "2" will be removed and 
the counting out begins at "3"

Step 2: Instead of finding the solution for the above diagram, we can simply find the solution of the following diagram. Note that 3 is mapped to 0 and 4 is mapped to 1 and so on..

(To find the solution of the above diagram we use the same approach from step1. I'd like to ignore that part.)
The solution for n=4 and k=3 is 0.

Now look at the first diagram. We know that 0 is mapped to 3 in step2 which is the required solution.

Thanks to xorfire for teaching me this awesome problem.

Comments are welcome.