To answer this question of outputting the sequence of execution, a simulation is required. This means O(nk) complexity. It is impossible to get sequence of execution [which is O(n)] while seeking O(nlogn) time complexity at the same time. Because you must output every person to be executed, which is O(n).
kkonrad's reference to Range Trees yield a nice O(nlogn) solution. As others have pointed out, a circular linked list is an efficient data structure for this problem. I find 200_success' Java solution from Code Review to be very elegant and readable.
public class CircularGunmenIterator<T> implements Iterator<T> {
private List<T> list;
private Iterator<T> iter;
public CircularGunmenIterator(List<T> list) {
this.list = list;
this.iter = list.iterator();
}
@Override
public boolean hasNext() {
// Continue as long as there is a shooter and a victim
return this.list.size() >= 2;
}
@Override
public T next() {
if (!this.iter.hasNext()) {
// Wrap around, creating the illusion of a circular buffer
this.iter = this.list.iterator();
}
return this.iter.next();
}
@Override
public void remove() {
this.iter.remove();
}
public static void main(String[] args) {
// Create the gunmen
List<Integer> gunmen = new LinkedList<Integer>();
for (int i = 1; i <= 100; i++) {
gunmen.add(i);
}
// Shootout!
Iterator<Integer> ringIter = new CircularGunmenIterator<Integer>(gunmen);
while (ringIter.hasNext()) {
Integer shooter = ringIter.next();
Integer victim = ringIter.next();
System.out.printf("%2d shoots %2d\n", shooter, victim);
ringIter.remove(); // Bang!
}
System.out.println("Last one alive: " + gunmen.get(0));
}
}
There are some more details on Wikipedia for this Josephus problem (k = 2).
http://en.wikipedia.org/wiki/Josephus_problem