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: Feb. 25, 2021 — 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.