Puzzle 1 : Survivor Problem

Problem Statement : There are 100 people forming a circle and they are numbered from 1 to 100. They decide to kill each other using a sword, in following manner. At any point, person numbered n having a sword kills person numbered n+1 and passes the sword to n+2. This process doesnot stop until at the end only 1 person remains alive. Initially, person numbered 1 has the sword in hand. Calculate the survivor number. What about any general N ?

Solution

For various N, survivor number obtained is given below,





1 -> 1
2 -> 1
4 -> 1
8 -> 1

3 -> 3
5 -> 3



6 -> 5



7 -> 7

It is apparent from above pattern that when N is power of 2, Survivor is 1. Otherwise we have to add 2 to every number away from power of 2.



Method 1(Using Recursion):

1. Let Survivor number be 1


2. Until N is power of 2




1. Subtract N by 1


2. Add 2 to Survivor number

int checkPowerOfTwo(int num)
{
       return (num && !(num & (num - 1)));
}

int findSurvivor(int totPerson)
{
       int result = 1;
       while(!checkPowerOfTwo(totPerson)
         && totPerson > 0)
       {
               findSurvivor(--totPerson);
               result += 2;
       }
       return result;
}

int main (int argc,
                 char *argv[])
{

       int noOfPerson;

       // Check number of arguments passed
       if (argc != 2)
       {
               printf( "usage: %s N\n", argv[0] );
               printf( "\t where N is number of persons\n", argv[0] );
               return 1;
       }

       noOfPerson = atoi(argv[1]);

       if (noOfPerson == 0)
       {
               printf("Zero is not a valid input\n");
               return 2;
       }
       printf("Survivor is %d\n", findSurvivor(noOfPerson));
       return 0;
}

Method 2:

1. If N is power of 2, return 1


2. Find next lower power of 2 wrt to N


3. Find difference between N and result from step 2. Double and add 1






int checkPowerOfTwo(int number)
{
        return (number && !(number & (number - 1)));
}

int findIndexOfMsb(int number)
{
        int result = 0;
        while (number >>= 1)
        {
                result++;
        }
        return result;
}
int findSurvivor(int totPerson)
{
        if (checkPowerOfTwo(totPerson))
        {
                return 1;
        }
        return (1 + (totPerson - (1 << findIndexOfMsb(totPerson))) * 2);
}

int main (int argc,
          char *argv[])
{

    int noOfPerson;

    // Check number of arguments passed
    if (argc != 2)
    {
        printf( "usage: %s N\n", argv[0] );
        printf( "\t where N is number of persons\n", argv[0] );
        return 1;
    }

    noOfPerson = atoi(argv[1]);

    if (noOfPerson == 0)
    {
        printf("Zero is not a valid input\n");
        return 2;
    }
    printf("Survivor is %d\n", findSurvivor(noOfPerson));
    return 0;
}