#
*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 5Output : 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 aliveOutput : 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.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*
## 0 Comments