100 gunmen in circle kill next person

The question is here.


100 people are standing in a circle with gun in their hands. 1 kills 2, 3 kills 4, 5 kills 6 and so on till we are left with only one person. Who will be the last person alive. Write code to implement this efficiently.

Here is my Java implementation:

public static void main(String[] args) throws Exception {
    int numberOfGuys = 100;
    MyObject[] objetList = new MyObject[numberOfGuys];
    for(int i=1;i newList = new ArrayList();
        for (MyObject myObject:objetList) {
            if(myObject != null) {
                newList.add(myObject);
            }
        }
        objetList = new MyObject[newList.size()];
        for(int i=0;i<newList.size();i++) {
            objetList[i] = newList.get(i);
        }
        if(objetList.length==1) {
            oneElementLeft = true;
        }
    }
    System.out.println(objetList[0].getIndex());
}

I am not a math guy, so I do not really understand the clever solutions with formulas, recursion etc...

Any review or better code with explanations are welcome.

The accepted answer in the linked question uses a cirucular linked list, which is the data structure that most closely represents this situation. That answer shows how to do that implementation, so I'll instead focus on the approach you look to be taking, which can be equally valid if it produces equivalent results.

public static void main(String[] args) throws Exception {

Why does your main method throw Exception? This is useless and potentially confusing. Your code does not encounter any expected exceptions, so why are you telling the reader to expect one? The exception you are telling them to expect is any exception, which is itself completely unhelpful. If your program encounters an uncaught exception, it will die just the same. Drop the throws Exception.

int numberOfGuys = 100;

Here, this is fine, but many people would probably just move it outside the method as static final int NUMBER_OF_GUYS = 100; since it is essentially a constant (unless you are planning to vary it with input in another iteration of the program).

MyObject[] objetList = new MyObject[numberOfGuys];

Two major issues here. First is naming. MyObject is a terrible name that tells the reader nothing of the nature of this class. A better name might be Gunman or Shooter, etc. For the variable name, objetList is also a terrible name. First, it looks very close to objectList, which increases the possibility of misspellings. It also says little to the nature of the variable, and what it does say is wrong. The suffix "List" might be interpreted to mean that this is a List object, but it is not. A better name might be gunmen or shooters (preferably matching off of the class name of the objects it holds).

The second major issue is the data structure chosen. We know that we will be removing elements from this structure, but we also know this is not efficient with a primitive array. Either we delete by using nulls, having to check that condition through the loop, or we delete by making a copy of the array, sans an element, each time we remove an element. A data structure built for this type of scenario is a List. There are several to choose from, each giving a potentially different performance profile, but we can just pick one to start and change that later if performance demands are not met.

for(int i=1;i<numberOfGuys+1;i++) {
    objetList[i-1] = new MyObject(i);
}

First, spacing is important. It is much harder to read code that does not have spacing around operators and such. Second, you perform excess operations that confuse what the loop is doing. Rather than start at one, go to numberOfGuys + 1, and insert at index objetList[i-1], start at 0. It would look more like this:

for(int i = 0; i < numberOfGuys; i++) {
    objetList[i] = new MyObject(i + 1);
}

boolean oneElementLeft = false;
while(!oneElementLeft) {
    ...
    if(objetList.length==1) {
        oneElementLeft = true;
    }
}

(SPOILER: Read all the way through this part before changing the code.)

This code tells a story, but it has a lot of noise in it. We test against a boolean, and exit out of the loop if it changes. We will only change that boolean based on a boolean test (objetList.length == 1) checked at the end of the loop. We already have a loop structure that does this more succinctly: the do-while loop! We could rewrite it so that we just have do { ... } while(objetList.length != 1); So much cleaner! And wrong. The story this code tells is misleading, and is in fact buggy. If objetList.length is already 1, we don't want to do anything! What we want is a simple while loop without the need for the flag:

while(objetList.length > 1) {
    ...
}

for(int i=0;i<objetList.length;i++) {
    if(i != objetList.length-1 && (i+1)%2==1) {
        objetList[i+1]=null;
    }
    if(i == objetList.length-1 && objetList[i] != null) {
        objetList[0]=null;
    }

}

Again, spacing.

These conditionals do not really tell a clear story. First of note, (i+1)%2 == 1 is asking if i plus one is odd. What it is really asking, though, is if i is even, or the same thing more succinctly, i % 2 == 0. (You will also see this written as i & 1 == 0 on occasion). Looking more generally, though, we are nulling the odd elements, and the first element if the list is an odd length. The conditionals don't come out and say this clearly, though. We check if we are at the end of the list every iteration, and do something when we reach the end only under certain special conditions. It is not totally clear that the condition is when the list is an odd length, either. More clearly, we can write:

for(int i = 0; i < objetList.length - 1; i += 2) {
    objetList[i + 1] = null;
}

if(objetList.length % 2 == 1) {
    objetList[0] = null;
}

Also note the vertical spacing used here. We often need space in both directions to make code the most readable.

```
List newList = new ArrayList();
f

StackExchange Code Review Q#56951, answer score: 20