Solving using mathematical method

Question

Here is the question:

There are 100 person ( lets name them 1 to 100 ) whos task is to eliminate the next person to them and pass the killing tool to the next person alive.

Example:
1 must eliminate person 2 and pass the killing tool to the person 3 and so on.

The problem is, I must find the last person that is alive.

Now I want to solve the problem above using formula instead of array. The solution I thought is something like this.

I used Array of boolean the loop them while flagging the next index to false. Then looping again to find which item is remained true.

Thanks in advance

Wouldn't the answer just be "the person at the end of the line"? So the formula would be "the length of the list"? — neminem, Feb 21 '15 at 00:08
Are they in a line? A circle? Something weirder? Who gets the weapon after person 100? Who would person 100 kill? — genisage, Feb 21 '15 at 00:09
possible duplicate of [Fastest way to determine if an integer's square root is an integer](http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer) — neminem, Feb 21 '15 at 00:16
That's weird, I misclicked on the flag as a dup page, then I *didn't* submit the flag, so why did it post that comment? — neminem, Feb 21 '15 at 00:20

score 1 · Answer 1 · answered Feb 21 '15 at 00:26

The answer is not 99. Think about it in smaller terms as if there were only 10 people, the answer would not be 9. This is how the algorithm would run out:

1 kills 2 passes to 3 3 kills 4 passes to 5 5 kills 6 passes to 7 7 kills 8 passes to 9 9 kills 10 passes to 1 - now people are 1,3,5,7,9 1 kills 3 passes to 5 5 kills 7 passes to 9 - now people are 1,5,9 9 kills 1 passes to 5 5 kills 9; only 5 is remaining.

In order to implement this, put the values into an ArrayList, and remove the killed person until the size of the ArrayList is 1:

    int numPeople = 100;
    List<Integer> list = new ArrayList<Integer>();
    for(int i = 1; i <= numPeople; i++) list.add(i);

    int current = 0;
    while(list.size() > 1)
    {

        list.remove(current+1);
        current++;
        //Circle back around to the beginning
        if(current+1 >= list.size()) current = current - list.size();  
    }
    System.out.println(list.get(0));

Solving using mathematical method

1 Answers1