I realize that this is old, but I happened to look at it today.
Linear
I would tend to agree with those that say a List
and iterator
are the wrong tools for this job. You can implement pretty much the same algorithm with a Queue
with less code:
public static int findSurvivor(int n) {
final Queue<Integer> people = new ArrayDeque<>(n);
for (int i = 0; i < n; i++) {
people.add(i);
}
while (people.size() > 1) {
// remove the shooter and add back to the end of the list
people.add(people.remove());
// remove the victim
people.remove();
}
return people.remove();
}
This is linear in time, as you have to insert each person in the list in the first loop and then remove each person from the list (we also move \$n - 1\$ people to the end of the list).
Logarithmic
As previously noted, it is possible to do better than that. Each time we loop through, we shoot \$\lceil\frac{n}{2}\rceil\$ people, halving the survivors. If \$n\$ is now even, the first person survives. If odd, the first shooter is the last person shot. On the first iteration, 0 is the first person and shoots 1, an interval of 1. The interval doubles in size each iteration. If the first person is not shot, that same person is the first person for the next round. If the first person is shot, the person that the first person handed the gun becomes the next first person. So
public static int findSurvivor(int n) {
int first = 0;
int interval = 2;
while (n > 1) {
if (n % 2 == 1) {
// the first person was shot, so update the first person
first += interval;
}
interval *= 2;
n = (int)Math.floor(n / 2.0);
}
return first;
}
This is slightly more code but considerably faster asymptotically. This is \$\mathcal{O}(\log n)\$. I tested it against the first algorithm and it gave the same answer from 1 to 100,000.
Basically we loop until we only have one person left. The interval
doubles in size each iteration because half the people get shot. The number of people remaining (n
) halves each time.
Concrete example with 10000.
n |
first |
interval |
10,000 |
0 |
1 |
5000 |
0 |
2 |
2500 |
0 |
4 |
1250 |
0 |
8 |
625 |
0 |
16 |
312 |
32 |
32 |
156 |
32 |
64 |
78 |
32 |
128 |
39 |
32 |
256 |
19 |
544 |
512 |
9 |
1568 |
1024 |
4 |
3616 |
2048 |
2 |
3616 |
4096 |
1 |
3616 |
8192 |
Note that the 10,000, 0, 1 line occurs before the loop starts. Also, the first person changes four times.
My code is zero-indexed, so the 3616 means the 3617th person in the circle.
Constant
We can do even better though. It turns out that there is a constant time solution (assuming that taking the logarithm is a constant time operation). See here.
Porting that to Java gives
public static int findSurvivor(int n) {
return 2 * n - (1 << (Integer.SIZE - Integer.numberOfLeadingZeros(n)));
}
This gives the same answer as far as I was willing to run the logarithmic solution sequentially: 100,000,000. The linear solution gives the same answer through 100,000. Integer.MAX_VALUE
(thirty-two bit) gives a solution of 2,147,483,646 (the last person) under both this and the logarithmic solution. The linear solution can't allocate memory for the queue and throws a "java.lang.OutOfMemoryError: Java heap space" (didn't try to play with Java configuration to see if that was fixable).
Note: this too is zero-indexed, so if you compare to a one-indexed solution, the answers may be off.