# 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?

## Solution in C++ Programming Language

```
#include <iostream>
using namespace std;
int find_power(int n)
{
n = n | (n>>1);
n = n | (n>>2);
n = n | (n>>4);
n = n | (n>>8);
return ((n+1)>>1);
}
int main()
{
int nearest_power, n;
cout<<"Enter the number of people standing in a circle"<<endl;
cin>>n;
nearest_power = find_power(n);
int survivor = 2*(n - nearest_power) + 1;
cout<<survivor<<" will survive at last!";
return 0;
}
```

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.

## Another Solution in C++ Programming Language as Requested by a User

```
#include
```
using namespace std;
int find_power(int a, int b)
{
int e=1;
for(int i=0;i<b;i++)
{
e=e*a;
}
return e;
}
int main()
{
int survivor, num, k, i=0;
cout<<"Enter the number of people standing in a circle: ";
cin>>num;
for(int i=0;i<num;i++)
{
k=find_power(2,i);
if(k>num)
{
k=find_power(2,i-1);
int x=num-k;
survivor=(2*x)+1;
break;
}
}
cout<<survivor<<" will survive at last!";
return 0;
}

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.