Solution Code for Game of Circle puzzle in C

In this article we are going to solve and try to execute the Game of Circle problem in C Programming language.Before we start to solve this puzzle,First see the Problem and understand it.

Problem:-

Given N peoples situated in a place that place is in circle shape and that place a war is happened where a person is having gun, find the luckiest person in that place, if from 1st soldier who is having a gun each have to kill the next soldier and handover the gun to next soldier, in turn the soldier will kill the adjacent soldier and handover the gun to next soldier.

We have to find that one soldier who live and  remain in this war who is not killed in this war at that place and not killed by anyone.

Here some examples are given to better understand you how the output is shown on the screen of the PC.

Examples :-

Input : 7
Output : 5
Explanation :
N = 7
Soldier 1 2 3 4 5  6 7(7soldiers)
In first go 1 3 5 7 (remains) as 2 4  and 6 killed by 1 3 and 5.
In second go 5 as 7 killed 1st 3rd  and 5^th kill 7 soldier 3 remains alive.

Input : 100
Output : 73
Explanation :
N = 10
Soldiers 1 2 3 4 5 6 7 8 9 10 (10 soldiers)
In first 1 3 5 7 9 as 2 4 6 8 10 were killed by 1 3 5 7 and 9.
In second 1 5 9 as 9 kill 1 and in turn 5 kill 9th soldier.
In third 5 5th soldiers remain alive

Here as N = 8, 1 will shoot 1, 3 will shoot 4, 5 will shoot 6, 7 will shoot 8, Again 1 will shoot 3, 5 will shoot 7, Again 1 will shoot 5 and hence 1 is the soldier who alive in this war.

Approach :-

We use to solve this puzzle and for this we use circular linked list. A circular linked list is start with the total number of soldiers N. As rule state you have to kill your adjacent soldier and handover the sword to the next soldier who in turn kill his adjacent soldier and handover sword to the next soldier. So in circular linked list the adjacent soldier are killed and the remaining soldier fights against each other in a circular way and a single soldier survive who is not killed by anyone.

Algorithm:-

1.    Take the Binary Equivalent of N.

2.    Find its 1’s compliment and convert its equal decimal number N`.

3.    find |N – N`|.

Solution:-

#include <iostream>

structNode {

    int arg;

    structNode* next_value;

};

  

Node *Node1(int arg)

{

   Node *node = Node1;

   node->arg = arg;

   node->next_value = NULL;

   returnnode;

}

  

intsoldier_1(int value)

{

    if(value == 1)

        return1;

  

    

    Node *last = newNode(1);

    last->next_value = last;

      

    for(inti = 2; i <= value; i++) {

        Node *temp = Node1(i);

        temp->next_value = last->next_value;        

        last->next_value = temp;

        last = temp;     

    }

  

        Node *current = last->next_value;

  

    Node *temp;

    while(current->next_value != current) {

        temp = current;

        current = current->next_value;

        temp->next_value = current->next_value;

  

        deletecurrent;

        temp = temp->next_value;

        current = temp;

    }

  

    intres = temp->arg;

    deletetemp;

      

    returnres;

}

  

intmain()

{

    intN = 100;

    cout <<soldier_1(N) << endl;

    return0;

}

Output:

73

    -------------------OR------------------------

#include <iostream>

  

intconvert_str(string x)

{

  

    stringstream value(x);

  

    int y = 0;

    value>> y;

  

    return y;

}

  

intconvert_binary(string z)

{

    intnum = convert_str(z);

    intval = 0;

  

    

    int com = 1;

  

    inttemp = num;

    while(temp) {

        intdigit = temp % 10;

        temp = temp / 10;

  

        decimal_value += last_digit * com;

  

        com = com * 2;

    }

  

    returndecimal_value;

}

  

string soldier_1(intn, string string, int com)

{

    inti = 0;

    boolisNegative = false;

  

    if(n == 0) {

        string[i++] = '0';

        returnstring;

    }

  

    if(n < 0 && com == 10) {

        isNegative = true;

        n = -n;

    }

  

    while(n != 0) {

        intrem = n % com;

        string[i++] = (rem > 9) ? (rem - 10) + 'a': rem + '0';

        n = n / com;

    }

    if(isNegative)

        string[i++] = '-';

  

    reverse(string.begin(), string.end());

  

    returnstring;

}

  

char change(char w)

{

    return(w == '0') ? '1': '0';

}

  

string Complement(string binary)

{

    intn = binary.length(), i;

  

    string num = "";

  

    

    for(i = 0; i < n; i++)

        num += flip(binary[i]);

  

    return num;

}

  

intmain()

{

    intN = 3;

    string array = "";

  

    string answer(soldier_1(N, array, 2));

  

    int result = convert_binary(Complement(answer));

  

    int soldier = N - result;

  

    cout <<soldier;

  

    return0;

}

Output:

3