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  chairs = new ArrayList();
        for (int i = 0; i  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 "diamond operator". The following:

ArrayList chairs = new ArrayList();

should be:

ArrayList chairs = new ArrayList<>();

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 chairs = new ArrayList<>();

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 "walk the list". 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 chairs = new LinkedList<>();
    while (chairs.size()  1) {
        System.out.println("Eliminated " + chairs.removeFirst());
        skip++;
        int shift = skip % chairs.size();
        for (int i = 0; i < 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 "improved" my alternative suggestion to be a more natural language fit than an ArrayList (which does not have O(1) "remove" 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 -> 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 -> 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 > 1) {
        Chair togo = previous.next;
        previous.next = togo.next;
        togo.next = null;
        size--;
        int shift = (numChairs - size) % size;
        while (shift-- > 0) {
            previous = previous.next;
        }
    }
    return previous.id;
}

private static Chair buildCircle(int numChairs) {
    final Chair last = new Chair(numChairs);
    Chair tmp = last;
    while (--numChairs > 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 -> CL: (Unit: MICROSECONDS)
Count : 943355 Average : 3.1800
Fastest : 2.3680

StackExchange Code Review Q#88190, answer score: 7