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<Integer> chairs = new ArrayList<Integer>();
should be:
ArrayList<Integer> 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<Integer> 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<Integer> chairs = new LinkedList<>();
while (chairs.size() < numChairs) {
chairs.add(chairs.size() + 1);
}
int skip = 0;
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 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 "pointer" 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 "next" 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 <= 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 >= 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 -> 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 "remaining" 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 "back one spot" 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 < numChairs; i++) {
chairs[i] = i + 1;
}
int remove = 0;
int skip = 0;
int size = numChairs;
while (size > 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 -> 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.
