datastructures-Puzzle

Question

There are 5 members sitting around a table. Key value is the number of members sitting around the table. So now the key value will be 5. A terrorist told the members that as you are 5 members I will count from first member and the person who is counted 5 will be shot dead. He counts and the 5th person dies. Once again he counts up to five and the 1st person dies. Once again he counts and the 3rd person dies, and now 2 and 4 are remaining.He counts the no between them finally 4 will be counted as 5 and he is shot dead.The last person remaining will be 2.

Like the same if tried for seven persons the answer will be 8. And for 8 persons the answer will be 4.

How to set a formula for this so that computer can shoot the person correctly.

I guess it might be in a circular linked list by giving a token value to the members.But i could not arrive at an equation. So by giving the key value the person who will live will be determined.

Answer 1

This is a well known problem called Josephus problem. Check wikipedia and mathworld for possible solution. And you can use Google for numerous articles on it.

Answer 2

This is termed the Josephus problem.

Answer 3

it's classic problem named Josephus problem . it has recursive solution :

J (1) = 1 ; this is the basis

when n is even J(2n) = 2J(n) - 1

when n is odd J(2n + 1) = 2J(n) + 1