Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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<numberOfGuys+1;i++) {
        objetList[i-1] = new MyObject(i);
    }
    boolean oneElementLeft = false;
    while(!oneElementLeft) {

        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;
            }
        }
        List<MyObject> newList = new ArrayList<MyObject>();
        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.

share|improve this question
1  
Rethink your q, pls. Start from the end. 100 is killed by 99. Who kills 99? 98. Who kills 98? If you start with 1 kills 2, who kills 3? The way you stated it, 1 kills everyone :-P or, what do you mean? Draw with pencil and paper. –  Thufir Jul 13 at 20:19
5  
@Thufir For simplicity's sake, consider 5 people: 1 kills 2, (2 is dead), 3 kills 4, (4 is dead), 5 kills 1, (1 is dead, 2 is dead), 3 kills 5 (4 was already dead), 3 wins. –  Simon André Forsberg Jul 13 at 22:26
1  
ah, that's fine. I thought that the question had been mis-stated. In terms of an answer, I think it's necessary, or much easier, at least, to use a link list. –  Thufir Jul 13 at 22:41
    
@Thufir I do not think trying to go backwards will work for every problem on earth. :) Can you please provide a solution with LinkedList? I think it will be a little cleaner, you are right, but it will essentially work very similar, right? –  Koray Tugay Jul 14 at 5:17
    
@KorayTugay going "backwards" would only be applicable were it that 100 was killed by 99, who was killed by 98, etc. which is not your problem. which does not rule out recursion as being useful. I just wanted to be clear on what your problem was. –  Thufir Jul 14 at 8:56

6 Answers 6

up vote 16 down vote accepted
+100

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<MyObject> newList = new ArrayList<MyObject>();
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);
}

Here the code is basically just shuffling array data. This is the biggest indicator that a primitive array is the wrong data structure to be using.


I wrote the following version that accomplishes the same thing in a similar (non-circular) manner. It can probably be improved by using an iterator inside of it, but it suffices on its own.

Main class:

public class Main
{
    public static final int NUMBER_OF_GUNMEN = 100;

    public static void main(String[] args) {
        List<Gunman> gunmen = new ArrayList<>(NUMBER_OF_GUNMEN);
        for(int i = 1; i <= NUMBER_OF_GUNMEN; i++) {
            gunmen.add(new Gunman(i));
        }

        while(gunmen.size() > 1) {
            for(int i = 0; i < gunmen.size(); i++) {
                Gunman killer = gunmen.get(i);
                Gunman killed = gunmen.remove((i + 1) % gunmen.size());
                System.out.println(killer.getNumber() + " kills " + killed.getNumber());
            }
        }

        System.out.println("\n" + gunmen.get(0).getNumber() + " lives another day...");
    }
}

Gunman class:

public class Gunman
{
    private int number;

    public Gunman(int number) {
        this.number = number;
    }

    public int getNumber() {
        return number;
    }
}
share|improve this answer
    
Thanks, great comments. You are right in most of (if not all) of your comments. Also Oracle suggests convention: for (initialization; condition; update) { statements; } so I will fix my template according to this! –  Koray Tugay Jul 14 at 5:18
2  
The code is simple, which is nice. However, the problem asks for efficient code, and ArrayList.remove() is not efficient. The first shot, killing number 2, causes 98 elements to be copied over. –  200_success Jul 14 at 5:38
    
@200_success You are right. My code tries to mirror his approach. I address performance at three points. First, I note that circular linked list is the most correct structure to use. Later, I note that we can vary which list structure we use through polymorphism based on performance criteria. Finally, I note that my implementation can be improved with iterators. All in all, with ArrayList or with LinkedList, 100 elements gets done in ~0.1s for me. The efficiency in this is that I put working code up now instead of spending 20 minutes researching Java lists to optimize milliseconds. –  cbojar Jul 14 at 15:11
    
Fair enough. I've upvoted it as a very thorough answer. –  200_success Jul 14 at 15:14
    
While your answer is correct and good (voted for it) I do have 2 smaller issues to make : First of all your list of gunmen. It contains 100 gunmen so at least it has to be plurial. Secondly in OO I do not like to see logic in the static void main except building your testcase. Your 4 first lines are correct (maybe it could be in a method), but your last line should be like System.out.println("\n" + GunMenShotDown.whoStands(players).getNumber() + " lives another day..."). (Very important when doing test cases in job interviews) –  chillworld Jul 29 at 5:15

Sometimes math can be confusing, sometimes it can help, but, using some math, the solution to this problem is:

public static final int getSurvivingGunman(int startCount) {
    return 1 + (startCount - Integer.highestOneBit(startCount)) * 2;
}

Your main method would look like:

public static void main (String[] args) {
    System.out.println(getSurvivingGunman(100));
}

Which produces:

73

Now, as to why it works, consider the problem:

  • If there are exactly 2 gunman, then 1 is the survivor.
  • If there are exactly 4 gunman, then after the first round, there are two gunman, and again 1 survives.
  • if the number of gunman is an exact power of 2, then the survivor is gunman 1.

That's easy, but, what about other sizes....

All powers of 2 are even (after 20), so, if you add a single gunman, the first 'round' will be odd, and the last gunman will shoot the first gunman, which means the next round will start from gunman 2, which, in effect, skips ahead two.

Essentially, for each gunman after the previous power of 2, the surviving gunman is 2 ahead.

Java makes finding the previous power of 2 easy with the Integer.highestOneBit(int) function, and the rest is easy.

If you run it with the main method:

public static void main(String[] args) {
    for (int start = 0; start <= 100; start++) {
        System.out.printf("%3d gunmen has %3d survivor%n", start, getSurvivingGunman(start));
    }
}    

the pattern is more obvious.

Also, since the algorithm is \$O(1)\$ time complexity, you can do things like:

    for (int start = 10; start <= 1000000000; start *= 10) {
        System.out.printf("%3d gunmen has %3d survivor%n", start, getSurvivingGunman(start));
    }

and get the results (fast):

 10 gunmen has   5 survivor
100 gunmen has  73 survivor
1000 gunmen has 977 survivor
10000 gunmen has 3617 survivor
100000 gunmen has 68929 survivor
1000000 gunmen has 951425 survivor
10000000 gunmen has 3222785 survivor
100000000 gunmen has 65782273 survivor
1000000000 gunmen has 926258177 survivor
share|improve this answer

Critique

I think the following code was implied:

public class MyObject {
    private int index;

    public MyObject(int i) {
        this.index = i;
    }

    public int getIndex() {
        return index;
    }

    public static void main(String[] args) {
        …
    }
}

That works, but MyObject is the least informative name for a class possible. Gunman would be much better. Similarly, I suggest renaming objetList to gunmen.

The oneElementList variable is pointless. You could just say

while (objetList.length != 1) { … }

Reconsolidating the list after reaching the end is inefficient. You want to either implement a , or as I've done below, simulate a circular buffer by using an iterator. Since the problem calls for elements to be spliced out frequently, this is one of those rare situations where a is useful.

Suggested solution

Since the code for the shootout loop can get rather complex, it's worth making an effort to simplify it. By using an iterator, we can relieve ourselves of the need to use any array indices at all.

In this problem, a gunman is just a number. I've represented it using an Integer.

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));
    }
}
share|improve this answer
    
Great solution, thank you very much. Very clear as well. –  Koray Tugay Jul 14 at 5:20

I have tried to solve this problem with recursion:

package com.study.recursion;

import java.util.List;

public class GunMens {
    private static final int SECOND_ELEMENT = 1;
    private static final int FIRST_ELEMENT = 0;
    public Integer killingStartsFrom(int gunManWhokillsNextPerson,List<Integer> groupOfGunMens) throws Exception{
        if(groupOfGunMens.size() ==0){
            throw new Exception("No GunMen is present .. Cannot continue Killing :)");
        }
        if(groupOfGunMens.size()==1){
            return groupOfGunMens.get(FIRST_ELEMENT);
        }
        else if(groupOfGunMens.size() ==2){
            if(gunManWhokillsNextPerson==SECOND_ELEMENT){
                return groupOfGunMens.get(SECOND_ELEMENT);
            }else {
                return groupOfGunMens.get(FIRST_ELEMENT);  
            } 
        }
        else if(gunManWhokillsNextPerson == groupOfGunMens.size()-1){
            groupOfGunMens.remove(FIRST_ELEMENT);
            return killingStartsFrom(FIRST_ELEMENT,groupOfGunMens);
        }
        else if(gunManWhokillsNextPerson+1 == groupOfGunMens.size()-1){
            groupOfGunMens.remove(gunManWhokillsNextPerson+1);
            return killingStartsFrom(FIRST_ELEMENT,groupOfGunMens);
        }
        else{
            groupOfGunMens.remove(gunManWhokillsNextPerson+1);
            return killingStartsFrom(gunManWhokillsNextPerson+1,groupOfGunMens);    
        }
    }
}

Benefits of this program:

  1. This will give you the same output which the program in the question will give.
  2. This program additionally provides ways to specify who should start shooting (i.e. shooting may start from third-person and the survivor would be different in this case).

Scenarios covered in this program:

  1. If no gumman is present then program says 'cannot continue killing :)' (notice the smiley at the end).

  2. If only one gunman is present then he is the survivor.

  3. If two gunmen are there then only two scenarios to be tested, anyone who starts shooting will be the survivor.

  4. Multiple gunmen in each call/recursion. A gunman will kill the next person until only two gunmen are remaining.

  5. Killing can start from any gunmen for e.g. fourth in 100 gunmen can start shooting.

I have written the below test class which has Junits written to test the behavior:

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.List;
import org.junit.Test;
import com.study.recursion.GunMens;

public class GunMensTest {
 GunMens mens = new GunMens();

    @Test(expected =Exception.class)
    public final void test_NoGunMen_ShouldThrowException() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        Integer gunMenSurvived = mens.killingStartsFrom(0, gunmens);
        assertEquals(gunMenSurvived,new Integer(0));
    }
    @Test
    public final void test_OneGunMen_HeShouldBeTheSurvivor() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);
        Integer gunMenSurvived = mens.killingStartsFrom(0, gunmens);
        assertEquals(new Integer(1),gunMenSurvived);
    }
    @Test
    public final void test_TwoGunMen_OneWhoStarts_isTheSurvivor() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);
        Integer gunMenSurvived = mens.killingStartsFrom(0, gunmens);
        assertEquals(new Integer(1),gunMenSurvived);
    }
    @Test
    public final void test_TwoGunMen_OneWhoStarts_isTheSurvivor_2() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);
        Integer gunMenSurvived = mens.killingStartsFrom(1, gunmens);
        assertEquals(new Integer(2),gunMenSurvived);
    }

    @Test
    public final void test_FourGunMen_ShootingStartsWithFirstPerson() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);gunmens.add(3);gunmens.add(4);
        Integer gunMenSurvived = mens.killingStartsFrom(0, gunmens);
        assertEquals(new Integer(1),gunMenSurvived);
    }
    @Test
    public final void test_FourGunMen_ShootingStartsWithSecondPerson() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);gunmens.add(3);gunmens.add(4);
        Integer gunMenSurvived = mens.killingStartsFrom(1, gunmens);
        assertEquals(new Integer(2),gunMenSurvived);
    }

    @Test
    public final void test_FourGunMen_ShootingStartsWithThirdPerson() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);gunmens.add(3);gunmens.add(4);
        Integer gunMenSurvived = mens.killingStartsFrom(2, gunmens);
        assertEquals(new Integer(3),gunMenSurvived);
    }

    @Test
    public final void test_FourGunMen_ShootingStartsWithFourthPerson() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);gunmens.add(3);gunmens.add(4);
        Integer gunMenSurvived = mens.killingStartsFrom(3, gunmens);
        assertEquals(new Integer(4),gunMenSurvived);
    }

    @Test
    public final void test_FiveGunMen_ShootingStartsWithFirstPerson() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);gunmens.add(3);gunmens.add(4);gunmens.add(5);
        Integer gunMenSurvived = mens.killingStartsFrom(0, gunmens);
        assertEquals(new Integer(3),gunMenSurvived);
    }

    @Test
    public final void test_FiveGunMen_ShootingStartsWithThirdPerson() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);gunmens.add(3);gunmens.add(4);gunmens.add(5);
        Integer gunMenSurvived = mens.killingStartsFrom(2, gunmens);
        assertEquals(new Integer(5),gunMenSurvived);
    }

    @Test
    public final void test_FiveGunMen_ShootingStartsWithFifthPerson() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);gunmens.add(3);gunmens.add(4);gunmens.add(5);
        Integer gunMenSurvived = mens.killingStartsFrom(4, gunmens);
        assertEquals(new Integer(2),gunMenSurvived);
    }

    @Test
    public final void test_SixGunMen_ShootingStartsWithFifthPerson() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        gunmens.add(1);gunmens.add(2);gunmens.add(3);gunmens.add(4);gunmens.add(5);gunmens.add(6);
        Integer gunMenSurvived = mens.killingStartsFrom(4, gunmens);
        assertEquals(new Integer(3),gunMenSurvived);
    }
    @Test
    public final void test_HundredGunMen_killingStartsFromFirst() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        for(int i =0; i<100;i++){
            gunmens.add(i+1);
        }
        Integer gunMenSurvived = mens.killingStartsFrom(0, gunmens);
        assertEquals(new Integer(73),gunMenSurvived);
    }

    @Test
    public final void test_HundredGunMen_killingStartsFromSecond() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        for(int i =0; i<100;i++){
            gunmens.add(i+1);
        }
        Integer gunMenSurvived = mens.killingStartsFrom(1, gunmens);
        assertEquals(new Integer(74),gunMenSurvived);
    }

    @Test
    public final void test_HundredGunMen_killingStartsFromTenth() throws Exception {
        List<Integer> gunmens = new ArrayList<Integer>(); 
        for(int i =0; i<100;i++){
            gunmens.add(i+1);
        }
        Integer gunMenSurvived = mens.killingStartsFrom(9, gunmens);
        assertEquals(new Integer(82),gunMenSurvived);
    }

     @Test
    public final void test_ThousandGunMen_killingStartsFromFirst() throws Exception {
      List<Integer> gunmens = new LinkedList<Integer>(); 
        for(int i =0; i<1000;i++){
        gunmens.add(i+1);
    }
    Integer gunMenSurvived = mens.killingStartsFrom(0, gunmens);
    assertEquals(new Integer(977),gunMenSurvived);
  }
}

Scope of improvement:

This program throws a stack overflow exception if tried with 10000 gunmen. But I believe the problem statements is 100 gunmen, hence this solution will serve its purpose.

share|improve this answer
1  
Your if-elseif statements could use some improvement, but it's awesome that you've included unittests with your answer! –  Pimgd Jul 29 at 13:15

Both @cbojar and @200_success' code solutions are great for this problem. Linked list iterator is definitely more efficient for this problem as others have pointed out.

As a minor side note, in @cbojar's final solution, it's missing Gunman in the ArrayList initialization.

List<Gunman> gunmen = new ArrayList<>(NUMBER_OF_GUNMEN);

If you're interested: mathematically, this is Josephus problem with k = 2. It was proven via induction, and details can be found here.

share|improve this answer
6  
Since Java 7, we've had the diamond operator, which means we don't need the explicit reference to Gunman in the initialization any more. If this were <= Java 6 though, you would be right. –  cbojar Jul 28 at 3:28

This is a special case of Josephus problem:

There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

100 gunmen scenario described in the question is equivalent to josephus(100, 2, 1). To get entire sequence use

import java.util.*;

public static void main(String[] argv) 
{
    System.out.println(josephus(100,2,1));
}

Last man standing is on position josephus(100,2,1).get(99).

Most efficient in case of step == 2 is analytical solution (see @rolfl 's answer) with O(1) run time.

If step parameter changes from from 2 to 3 or more, run time increases to O(N).

// remove N elements in equal steps starting at specific point
static List<Integer> josephus(int N, int step, int start)
{
    if (N < 1 || step < 1 || start < 1) return null;

    List<Integer> p = new LinkedList<Integer>();
    for (int i = 0; i < N; i++)
        p.add(i+1);

    List<Integer> r = new LinkedList<Integer>();
    int i = (start - 2) % N;
    for (int j = N; j > 0; j--) {
        i = (i + step) % N--;
        r.add(p.remove(i--));
    }

    return r;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.