The last standing gunman in a circle

Question

I don't know why in most of the interviews, interviewers are asking this question commonly.

The question is: There are n number of persons standing in a circle. The first person has a gun and he kills the very next person who is alive and hands over the gun to the next person. Who will remain?

Here is my code for the above scenario. It works, if anyone needs to ask.

public static void void main(String ar[]) {

    int numberOfGuys = 10000;
    List<Integer> list = new ArrayList<>();
    for ( int i = 1; i <= numberOfGuys; i++ ) {
        list.add( i );
    }
    boolean isNeighbour = false;

    System.out.println( list );
    Iterator<Integer> i = list.iterator();
    list = new ArrayList<>();
    boolean isTrue = true;
    while ( isTrue ) {
        int k = i.next();
        if ( isNeighbour )
            i.remove();
        else {
            list.add( k );
        }
        if ( !i.hasNext() ) {
            System.out.println( list );
            i = list.iterator();
            if ( list.size() == 1 )
                isTrue = false;
            list = new ArrayList<>();
        }
        isNeighbour = !isNeighbour;
    }
}

Answer 1

Style review

• I think numberOfGuys should be a parameter obtained in the main args, so that you respect the possibility to obtain n from an external source.

• As pointed in the comments, don't do isTrue = false, that's... weird. True is always true, period. You could rename it hasRemainingGuys or something like that.

Data structure

Using an ArrayList probably isn't the best data structure for your problem. This data structure is fast when it comes to obtaining data, but removing elements from it, which you do a lot, is slower. You'd want a structure where Remove is an \$O(1)\$ operation and, obviously, where it's easy to navigate from one element to the next. The LinkedList sounds like a good idea, as I'll point out below.

Alternative algorithm

I'd recommend creating some sort of circular linked list, so you wouldn't need to recreate the iterator when you reach the end of the list and to simplify some conditions. The idea is to have a linked list, where the last node's "next node" is the first one. This way, your generator could run until there's no next values.

Iterator<Integer> iterator = circularLinkedList.iterator();
//To start with the "first guy"
int k = -1;
while (iterator.hasNext()) {

    //Move on to the next shooter
    k = iterator.next();

    if (!iterator.hasNext()) {
        break;
    }

    //Move to the next shoot...ee?
    iterator.next();
    iterator.remove();
}

And... yeah, that's all. k contains the last guy standing.

Now, you need to implement a circular linked list and create an iterator that works with it. There are many examples on internet on how to do this.

You could also explore an option where you don't actually remove the element from the list, but simply keep a boolean where an index is flagged as dead or not. This might also be faster.

Answer 2

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.

Answer 3

I think the existing reviews are alright, but as it is an interview question, start to seek some intelligence for a solution. Often this will short-circuit evaluation with the use of differences, modulo and so on.

So as a review criticism: take a step back and take a simpler route. Show intelligence.

In a first round of shooting only the even people shoot and survive. The winner is in binary xxxx0.

public int solve(int n) {
    return solve("", n, true);
}

private int solve(String binary, int n, boolean startAt0) {
    if (n == 0 && binary.isEmpty()) {
        return -1;
    }
    if (n <= 1) {
        return Integer.parseInt(binary, 2);
    }
    String digit = startAt0 ? "0" : "1";
    if (n % 2 == 0) {
        return solve(digit + binary, n / 2, startAt0);
    } else {
        return solve(digit + binary, n / 2, !startAt0);
    }
}

I did not test it, but I think this is more impressive. In fact it even requires less thought and coding effort. Even if the result is wrong (I cannot entirely believe it is correct), the logic is persuasive.

Add some comments afterwards (// every second dies.).

If the solution came fast, do:

for (int i = 0; i < 20; ++i) {
    int survivor = solve(i);
    System.out.printf("n = %d, survivor = %d%n", i, survivor);
}
System.out.printf("n = %d, survivor = %d%n", 1000, solve(1000)); // Speed!

You can manually check a solution.

You might even add a dumb solution too, and check against that one in the for loop.

Answer 4

Bug

This code doesn't compile. That's a really low bar which you should be sure you cross before submitting it for review.

Structure

The main method should at most handle I/O. The calculation should be in a separate method which takes an argument (the number of people in the circle) and returns the solution. There shouldn't be any debug printing.

Looking at the guard on the while loop, I would conclude that you don't know the break keyword. As an interviewer, that would be a red flag unless the job was advertised as open to people who don't know programming on the expectation that the company will train them. (Actually even break is unnecessary: the loop just needs to check the break condition).

Names

isTrue has been mentioned in comments and another answer. isNeighbour also warrants inspection: everyone is a neighbour. What matters is whether the person is a shooter or not.

Code complexity

There's no need to keep discarding list and refilling it.

Refactoring your code, we get down to

public static int josephus2(int numberOfGuys) {
    List<Integer> list = new ArrayList<>();
    for ( int i = 1; i <= numberOfGuys; i++ ) {
        list.add( i );
    }

    boolean isShooter = true;
    Iterator<Integer> i = list.iterator();
    while (list.size() > 1) {
        int k = i.next();
        if ( !isShooter ) i.remove();
        if ( !i.hasNext() ) i = list.iterator();
        isShooter = !isShooter;
    }

    return list.get(0);
}

As mentioned in another answer, LinkedList would be much more efficient for this than ArrayList because of all of the calls to Iterator.remove().

Even this is more complex than an approach which appends to a longer array and does one loop, trading memory for simplicity:

public static void flat(int numberOfGuys) {
    int[] pos = new int[numberOfGuys * 2 - 1];
    for (int i = 0; i < numberOfGuys; i++) pos[i] = i + 1;
    for (int shot = 0; shot < numberOfGuys - 1; shot++)
    {
        // Person at position 2*shot shoots person at position 2*shot+1 and goes to end of queue
        pos[numberOfGuys + shot] = pos[2 * shot];
    }
    return pos[numberOfGuys * 2 - 2];
}

Algorithmic complexity

These approaches loop once per shot, and there are \$n - 1\$ shots fired, so it takes \$O(n)\$ time and space. It's possible to solve the problem in \$O(\lg n)\$ time by thinking about who survives an entire turn round the circle.

• If there's only one person, they survive.
• If there's an even number of people, those in odd positions (one-indexed) survive and it's person 1's turn to shoot again.
• If there's an odd number of people, those in odd positions (one-indexed) survive and it's person \$n\$'s turn to shoot.