Last man standing in Java

The “Last man standing” is also called “Josephus problem”. Give a number n people standing in a circle, eliminate every kth one until the last one remain. This problem can be solved with linked list and recursion

Here we use circular linked list to solve Josephus problem. First, we build a Circular Linked List by adding n nodes. Then use a while loop to remove the kth node until only one left.

The following in the implementation of Last man standing in Java. Please note in this particular question the k is 2. We need to find the last two men alive in stead of last man.

Amazon Interview Question (CareerCup):
Last Man Standing: A king gathers all the men in the kingdom who are to be put to death for their crimes, but because of his mercy, he will pardon one. He gathers the men into a circle and gives the sword to one man. The man kills the man to his left, and gives the sword to the man to the dead man’s left. The last man alive is pardoned.
With 5 men, the 3rd is the last man alive.
Write a program that accepts a single parameter: a number N that represents the number of criminals to start with. The program should output the number of the last two men alive.
Example #1: myProgram 5
would output:
5, 3
Example #2: myProgram 7
would output:
3, 7

Java Code:

With 5 men, the last two standing are:
Second to last: 5, last: 3

With 7 men, the last two standing are:
Second to last: 3, last: 7

O Notation:
Time complexity: O(n)
Space complexity: O(n)

Java Coding Interview Pocket Book (2nd Edition)
Josephus problem solution using recursion

Comments are closed