Question

1000 people are standing in a circle,next to each other i.e. 1 next to 2,2 next to 3 and so on,finally 1000 next to 1. Their names are 1,2,3...1000. 1 has a sword ; he kills 2 and hands the sword to 3.Then 3 kills 4 and hands it to 5. It goes on.finally 999 kills 1000 and gives is to 1 again. Then 1 kills the person next to him i.e. 3 and gives it to 5. 5 kills 7 and gives to 9 etc
Ultimately, only 1 person will name. What no. will that be?

Answer 1

i'm actually interested in finding a programming soln if possible ; but i couldn't crack the logic till now..
mathematical approach will also do good..

Answer 2

A programming solution sounds cool... Sounds like a set and a while loop would be the best bet...

Answer 3

1

Answer 4

am afraid 1 is not the ans i'd guess..

Answer 5

then

Answer 6

am sorry i dont remember the ans :P
but not 1,,its some 3 digit no.

Answer 7

came across this ques long time ago..
recalled it now..

Answer 8

God I want to write this program now, but all of my language skills are dead... WHERE DID THEY GOOO

Answer 9

Is there a command that will remove an element from a set?

Answer 10

Create a 1000 element set of integers numbered 1-1000.
int n=1
While(size of set >1)
{remove element number n+1
n= n+2
}

Answer 11

Does that work? God tell me that works and is codeable.

Answer 12

Oh flutter, I almost had it. Simple tweak:
Create a 1000 element set of integers numbered 1-1000.
int n=1
int setsize = 1000
While(setsize >1)
{
if(n <setsize)
{remove element number n+1
setsize--
n= n+1}
else
{remove element number 1
setsize--
n=1}
}

Answer 13

Oh, and then the last line would be just to output the only element left in the set.

Answer 14

@shubhamsrg any thoughts on my solution? Think it's sound?

Answer 15

@SmoothMath i think it can be done easily using circular queue ... using pointers.

Answer 16

i'd be back to it @SmoothMath

Answer 17

486 ?

Answer 18

Sorry, is it 257?

Answer 19

perl code for this :
cant think of solving this without program.... there must be some cute solution :/
my @people = (0 .. 999);
my $n = 1;
while( 1) {
my $tmp = splice(@people, $n, 1,);
if (($tmp eq undef) && ($#people)) {$n = $#people % 2 ? 0 : 1;next;}
if (($tmp eq undef) && (! $#people)) {exit;}
print "$n $tmp\n";
$n += 1;
}

Answer 20

i dont remember the ans..you might need to post your approach here..

Answer 21

@ganeshie8
486 cant be the ans,,infact,,no even no. can be the ans..
and i also didnt understand the coding much am sorry..am not very good at C++..

Answer 22

Numbers of the following form are eliminated easily,
2k
4k-1
8k-3
After this, since 1000 is not divisible by 16 the number 1 is eliminated from the list, but the pattern continues
16k-7
32k-15
64k-31
128k-64
256k-127
512k-128,
all the numbers of this form are deleted at some point, the last one being of the form 512k-128....not sure about this since the deletion process wraps around 1000 and the order of the elements becomes modular. Just my guess.

Answer 23

typo, of the form 512k-255

Answer 24

Okay. in program count starts with 0. so answer is 486 + 1 = 487.

thinking how to solve it w/o program..

Answer 25

gotcha @ganeshie8
altough i'll try n conc on the coding here..

Answer 26

noo... that i tried only to visualize..
@jlvm approach looks good to start with.. .

Answer 27

actually.. that program requires a small fix. answer is : 744

my @people = (0 .. 999);
my $n = 1;
while( 1) {
my $tmp = splice(@people, $n, 1,);
if (($tmp eq undef) && ($#people)) {$n = $#people % 2 ? \(\textbf{1 : 0}\);next;}
if (($tmp eq undef) && (! $#people)) {exit;}
print "$n $tmp\n";
$n += 1;
}

this seems hard without program :\

Answer 28

744 + 1

Answer 29

#include <iostream>

using namespace std;

int main()
{
bool integers[1000];
int done=0;
int counter=0;

//Initialize everything to true
for(int k=0; k<1000; k++)
{
integers[k]=true;
}



while(done!=1000)
{
if(integers[counter%1000]==true)
{
int innerCounter=0;
bool finish=false;

while(!finish)
{
innerCounter++;
if(integers[(counter+innerCounter)%1000]==true)
{
integers[(counter+innerCounter)%1000]=false;
finish=true;
counter=(counter+innerCounter)%1000;
done++;
cout<<done<<" <deletion> "<<counter+1<<endl;
}
}
}
counter++;

}

cout << "Hello world!" << endl;
return 0;
}

Answer 30

That's my code, the answer is 977.

Answer 31

@jlvm amazing !!
you have used mods very nicely:) i messed up the code by avoiding mods and shrinking the array :\

Answer 32

Thank you :-)