# 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:**May 8, 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.