100 people are standing in a circle numbered 1 to 100. Person 1 kills the next person (i.e. No. 2) with a sword and gives the sword to the next to next person (i.e. No.3). All of them do the same until only one survives. Which number survives at last?


Updated: Nov. 27, 2020 — Training Time: 2 minutes
Overseen by: Archangel Macsika

Topic: Data Science.

Difficulty: Easy.

Companies who previously asked this: -

Objective: 100 people are standing in a circle numbered 1 to 100. Person 1 kills the next person (i.e. No. 2) with a sword and gives the sword to the next to next person (i.e. No.3). All of them do the same until only one survives. Which number survives at last?

Short Answer: No. 73.

Full Solution

If you understand the concept used here, you will always be able to solve this type of question regardless of what the n is.

The Algorithm used is recursion with the formula 2n+1.
Where n is the value you get when you use the given n value to subtract the closest power of 2 to the given n number but less than it.

The given n value is 100.
Since there are 100 people, the closest power of 2 will be 64 and 128.
However, 128 is greater than 100. So, we go with 64.

Therefore, n = 100 - 64
n = 36

Now, we can apply the formula 2n + 1,

(2 * 36) + 1
= 72 + 1
= 73.

Therefore the number that survives is No. 73.

You can get the solution here in written codes.

Was this training resource helpful?