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 5th kill 7 soldier 3 remains alive.
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 5th 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
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
0 Comments