Suppose there are n people standing in a circle. Person no.1 has a sword and he uses it kill no.2 and passes it onto person no.3. All the persons does the same until only 1 survives. Which number will survive at last and what algorithm can be applied to solve this?
Answers
Answered by
1
Answer:
The number 73 survives.
Consider the case when there are 2^n numbers in the circle. Each time the number reduces by half and the number 1 remains till the end.
In the given question, 1 kills 2, 3 kills 4 and so on till 71 kills 72. 36 people have been killed till now. 64 people remain in the circle. 64 is a power of 2. So the first guy after 72 will be the new number 1 in a circle of 2^6. So 73 will survive.
Similar questions