Survivor programming challenge I am working on a survivor problem:


  Complete Question Text: Take a second to imagine that you are in a
  room with 100 chairs arranged in a circle. These chairs are numbered
  sequentially from One to One Hundred.
  
  At some point in time, the person in chair #1 will be told to leave
  the room. The person in chair #2 will be skipped, and the person in
  chair #3 will be told to leave. Next to go is person in chair #6. In
  other words, 1 person will be skipped initially, and then 2, 3, 4..
  and so on. This pattern of skipping will keep going around the circle
  until there is only one person remaining.. the survivor. Note that the
  chair is removed when the person leaves the room.
  
  Write a program to figure out which chair the survivor is sitting in.


Below is the code I have:

public class ChairProblem {

    public static void main(String[] args) {
        System.out.println(getSurvivors(100));
    }

    private static int getSurvivors(int numChairs) {
        if (numChairs &lt; 1) {
            return -1;
        }

        // populate chair array list
        ArrayList&lt;Integer&gt; chairs = new ArrayList&lt;Integer&gt;();
        for (int i = 0; i &lt; numChairs; i++) {
            chairs.add(i + 1);
        }

        // removing all but one elements
        int indexOfChair = 0;
        int count = 1;
        while (chairs.size() &gt; 1) {
            chairs.remove(indexOfChair);
            indexOfChair += count;// skip the count number of chairs
            count++; //increase the number of chairs to skip by 1
            indexOfChair %= chairs.size();// loop to beginning if necessary
        }

        return chairs.get(0);
    }
}


How can this be improved? I was asked this question in an interview and I gave this answer, but I'm not sure whether this can be improved in terms of complexity or Java Docs as well.
Basics
In Java, since version 7, there is no need to specify the generic type of a generic class on the right-hand side of the initializer. Instead, you can use the &quot;diamond operator&quot;. The following:

    ArrayList&lt;Integer&gt; chairs = new ArrayList&lt;Integer&gt;();


should be:
    ArrayList&lt;Integer&gt; chairs = new ArrayList&lt;&gt;();

Additionally, unless you have a specific need, you should use the highest level of abstraction that's useful for your variables. There is no need to declare chairs as an ArrayList, when a List would be fine:
    List&lt;Integer&gt; chairs = new ArrayList&lt;&gt;();

Data Types
Here you have used an ArrayList, but this is a bad choice. Performance in ArrayLists is poor when you add or remove items from the middle of the list. A LinkedList is generally better for that type of operation.
Alternate solution
A linked list is a great option for this problem, because it can be made to behave like a circle. What we do, is start with a populated list, and then &quot;walk the list&quot;. We remove the first member, then take the next member, and move them to the end of the list. Then we remove the third member, and the 4th and 5th survive and go to the end. Note that the first, second, and third survivors (chair 2, 4, and 5) are now next to each other at the end.... (after chair 100).
Note that for every member we remove from the list, we add a bunch of survivors  to the end. By doing some modulo arithmetic, the amount we shift to the end can be controlled to the size of the remaining members.
We repeat the process until the list is size() == 1
private static int getSurvivorsLL(final int numChairs) {
    Deque&lt;Integer&gt; chairs = new LinkedList&lt;&gt;();
    while (chairs.size() &lt; numChairs) {
        chairs.add(chairs.size() + 1);
    }
    int skip = 0;
    while (chairs.size() &gt; 1) {
        System.out.println(&quot;Eliminated &quot; + chairs.removeFirst());
        skip++;
        int shift = skip % chairs.size();
        for (int i = 0; i &lt; shift; i++) {
            chairs.addLast(chairs.removeFirst());
        }
    }
    return chairs.removeFirst().intValue();
}

Note that, because I need the removeFirst() method, I use the Deque personality for the LinkedList.
Update - Neat, Custom, or Fast
This question got me thinking, for both good, and bad reasons. I initially misread the question, and gave a broken answer. Then I &quot;improved&quot; my alternative suggestion to be a more natural language fit than an ArrayList (which does not have O(1) &quot;remove&quot; time).
Unfortunately, for me, I then ran a benchmark against my code, and the OP's code. My code lost, even though the LinkedList is a more natural fit for this problem. It just makes sense that the LinkedList should be faster... all we are doing is shuffling items one-at-a-time to the end of the list. and there's only one item moved each turn. So, why was it slow? To put things in perspective, here are the times of the OP's code:
Task Chairs -&gt; OP: (Unit: MICROSECONDS)
  Count    :   1000000      Average  :    2.3310
  Fastest  :    1.9730      Slowest  : 1878.1240
  95Pctile :    2.7630      99Pctile :    3.9480
  TimeBlock : 2.506 2.323 2.245 2.479 2.268 2.262 2.265 2.262 2.386 2.319
  Histogram : 981012 14462  4176   229    97    13     5     3     1     2

It computes the solution for 100 chairs in under 2 microseconds. But the time for the LinkedList solution I propose is:
Task Chairs -&gt; LL: (Unit: MICROSECONDS)
  Count    :    182906      Average  :   16.4010
  Fastest  :   13.8150      Slowest  : 2252.3280
  95Pctile :   23.6840      99Pctile :   30.7890
  TimeBlock : 20.028 16.870 18.086 16.485 15.615 15.323 15.411 15.385 15.399 15.417
  Histogram : 179027  3537   253    52    15     2    16     4

where the fastest time is in about 14 mircoseconds - 7 times slower than the OP code, even though it in theory does less work!.
Right, so, what would make the code faster? First up, I designed a custom node class that would be simpler than a full Linked List. Here is the code:
private static final class Chair {
    private final int id;
    private Chair next = null;
    
    public Chair(int id) {
        this.id = id;
    }
    
}

private static int getSurvivorsCL(final int numChairs) {
    Chair previous = buildCircle(numChairs);
    int size = numChairs;
    while (size &gt; 1) {
        Chair togo = previous.next;
        previous.next = togo.next;
        togo.next = null;
        size--;
        int shift = (numChairs - size) % size;
        while (shift-- &gt; 0) {
            previous = previous.next;
        }
    }
    return previous.id;
}

private static Chair buildCircle(int numChairs) {
    final Chair last = new Chair(numChairs);
    Chair tmp = last;
    while (--numChairs &gt; 0) {
        Chair c = new Chair(numChairs);
        c.next = tmp;
        tmp = c;
    }
    last.next = tmp;
    return last;
}

The above code is a 'clean' version of what I would expect the circular chair arrangement to accomplish. What is the time for that?
Task Chairs -&gt; CL: (Unit: MICROSECONDS)
  Count    :     943355      Average  :     3.1800
  Fastest  :     2.3680      Slowest  : 34884.2530
  95Pctile :     3.5520      99Pctile :     3.9480
  TimeBlock : 3.243 3.098 3.068 3.160 3.478 3.202 3.241 3.047 3.127 3.137
  Histogram : 936200  2336  4519   169    84    29     3     1     2     4     4     2     1     1

This is 4 times faster than the LinkedList, but, it is still 50% slower than the OP's code? The 4-times faster than LinkedList is impressive, but there's still something that does not make sense to me.... it should be faster than ArrayList.
So, to experiment, I used an even simpler approach of a static array, where none of the data is moved at all. The only thing updated is a &quot;pointer&quot; to the next chair. In other words, the index in the array is essentially the chair number, and the value in the array is the &quot;next&quot; chair. This way we can create a logical circle, and just change a pointer each time a chair is removed. Here is the code:
private static int getSurvivorsAN(final int numChairs) {
    int[] chairs = new int[numChairs];
    for (int i = 1; i &lt;= numChairs; i++) {
        chairs[i - 1] = i % numChairs;
    }
    int current = numChairs - 1;
    int skip = 0;
    int size = numChairs;
    while (current != chairs[current]) {
        int remove = chairs[current];
        chairs[current] = chairs[remove];
        size--;
        skip++;
        int loopskip = skip % size;
        while (--loopskip &gt;= 0) {
            current = chairs[current];
        }
    }
    // chairs are 0-based, we need to return 1-based, so add 1.
    return current + 1;
}

How fast was that?
Task Chairs -&gt; AN: (Unit: MICROSECONDS)
  Count    :     939602      Average  :     3.1920
  Fastest  :     2.7620      Slowest  : 18780.0630
  95Pctile :     3.5530      99Pctile :     3.9470
  TimeBlock : 3.271 3.145 3.127 3.181 3.195 3.141 3.140 3.152 3.175 3.401
  Histogram : 934304   761  4360   114    47     9     3     2     0     1     0     0     1

About the same as the Chair node version above... but, still slower than the OP.
So, how to beat the OP? Well, it must boil down to the fact that a System.arrayCopy() of all the &quot;remaining&quot; chairs in the circle (what should be an O(n) operation, where n is the size of the List, is more efficient than looping over each value in the skip. So, for example, on the first iteration, we remove chair 1, it must mean that copying every other chair &quot;back one spot&quot; is faster than just moving 1 chair to the end. To test this, I made an efficient version of ArrayList (i.e. using primitives, not Integer). Here's the code:
private static int getSurvivorsAS(final int numChairs) {
    int[] chairs = new int[numChairs];
    for (int i = 0; i &lt; numChairs; i++) {
        chairs[i] = i + 1;
    }
    
    int remove = 0;
    int skip = 0;
    int size = numChairs;
    while (size &gt; 1) {
        size--;
        System.arraycopy(chairs, remove + 1, chairs, remove, size - remove);
        chairs[size] = 0;
        skip++;
        remove = (remove + skip) % size; 
    }
    return chairs[0];
}

How does this compare?
Task Chairs -&gt; AS: (Unit: MICROSECONDS)
  Count    :   1000000      Average  :    1.6140
  Fastest  :    1.1840      Slowest  : 1699.3120
  95Pctile :    1.9740      99Pctile :    2.3690
  TimeBlock : 1.653 1.614 1.573 1.689 1.593 1.591 1.592 1.583 1.650 1.606
  Histogram : 970982 26003   384  2495    78    35    17     4     1     0     1

So, what does this all mean?
Well, it means that System.arraycopy() is fast. How do things scale, though?
Here are the scaling charts for three of the code blocks, the OP code, the best Circular List code (with the Chair node), and the ArrayShift code.
All three have a O(n^2) type complexity, so it all washes out, essentially. Note that the array-shift code is fastest for all tested scales (all the way up to more than 100,000 chairs.
Conclusion
The OP's code is better than I expected in terms of performance. The LinkedList code is worse than I expected. The best code from a readability perspective is, I think, the LinkedList code. It best represents the actual problem.
The best code from a performance perspective is a primitive array-of-int which you shift using System.arrayCopy() in order to remove chairs.