Solution to Suppose there are n people standing in a circle. Person no.1 has a sword and … - Sikademy

Nov. 27, 2020

Archangel Macsika Sikademy Image

Archangel Macsika

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.

If you would like to see a different solution or an implementation in a different programming language Kindly let us know