“Josephus problem” or “circle of death problem”. Given a number n people standing in a circle, eliminate every kth one until the last one remain.
This problem can be solved with a circular linked list. First, we build a circular Linked List by adding n nodes. The number starts from 1 (not 0). Use two pointers prev and p to keep track previous and current node. Then a while loop is used to remove every kth node until the last man remaining.Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | public class LastManStanding { static class LinkNode { int data; LinkNode next = null; //Constructor, Time O(1), Space O(1) public LinkNode(int value) { this.data = value; } } //Two pointers, Time O(n), Space O(n), n is input number public static int lastMenStanding(int n, int m) { LinkNode head = new LinkNode(1); LinkNode prev = head; for (int i = 2; i <= n; i++) { //build circular linked list, starting from 1 prev.next = new LinkNode(i); prev = prev.next; } prev.next = head; //last node connects to head LinkNode p = head; prev = null; int remain = n; //number of nodes left in the list while (remain >= 1) { for (int i = 1; i < m; i++) { //move every other one prev = p; p = p.next; } prev.next = p.next; //remove the node from the list p = prev.next; remain--; } return p.data; } public static void main(String[] args) { int n = 7; int m = 3; System.out.print( "with " + n + " men, the last standing are "); System.out.println(lastMenStanding(n,m)); } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | class LinkNode { //Constructor, Time O(1), Space O(1) constructor(value) { this.data = value; this.next = null; } } //Two pointers, Time O(n), Space O(n), n is input number function lastManStanding(n, m) { var head = new LinkNode(1); var prev = head; for (let i = 2; i <= n; i++) { //build circular linked list, starting from 1 prev.next = new LinkNode(i); prev = prev.next; } prev.next = head; //last node connects to head var p = head; prev = null; var remain = n; //number of nodes left in the list while (remain >= 1) { for (let i = 1; i < m; i++) { //move every other one prev = p; p = p.next; } prev.next = p.next; //remove the node from the list p = prev.next; remain--; } return p.data; } let n = 7; let m = 3; console.log( "with " + n + " men"); p = lastManStanding(n,m); console.log("last man is " + p); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | class LinkNode : #Constructor, Time O(1), Space O(1) def __init__(self, value): self.data = value self.next = None #Two pointers, Time O(n), Space O(n), n is input number def lastMenStanding(n, m) : head = LinkNode(1) prev = head for i in range(2, n+1) : #build circular linked list, starting from 1 prev.next = LinkNode(i); prev = prev.next; prev.next = head; #last node connects to head p = head prev = None reamin = n #number of nodes left in the list while reamin >= 1: for i in range (1 , m): #move every other one prev = p p = p.next prev.next = p.next #remove the node from the list p = prev.next reamin -= 1 return p.data n = 7 m = 3 p = lastMenStanding(n, m) print("last man standing: " + str(p)) |
We can extend the solution to find last two men standing. We declare a variable left to check whether there are two left. If there are two left, return the prev‘s data which is the second to last. The implementation is in Java, JavaScript and Python.
Amazon Interview Question:
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | public class LastMenStanding { static class LinkNode { int data; LinkNode next = null; //Constructor, Time O(1), Space O(1) public LinkNode(int value) { this.data = value; } } //Two pointers, Time O(n), Space O(n), n is input number public static int lastMenStanding(int n) { LinkNode head = new LinkNode(1); LinkNode prev = head; for (int i = 2; i <= n; i++) { //build circular linked list, starting from 1 prev.next = new LinkNode(i); prev = prev.next; } prev.next = head; //last node connects to head LinkNode p = head; prev = null; int left = n; //number of nodes left in the list while (left >= 2) { if (left == 2) //second to last System.out.print("Second to last: " + prev.data); for (int i =1; i < 2; i++) { //move every other one prev = p; p = p.next; } prev.next = p.next; //remove the node from the list p = prev.next; left--; } return p.data; } public static void main(String[] args) { int n = 5; System.out.println( "with " + n + " men"); int p = lastMenStanding(n); System.out.println(", last: " + p); n = 7; System.out.println( "\nwith " + n + " men"); p = lastMenStanding(n); System.out.println(", last: " + p); } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | class LinkNode { //Constructor, Time O(1), Space O(1) constructor(value) { this.data = value; this.next = null; } } //Two pointers, Time O(n), Space O(n), n is input number function lastMenStanding(n) { var head = new LinkNode(1); var prev = head; for (let i = 2; i <= n; i++) { //build circular linked list, starting from 1 prev.next = new LinkNode(i); prev = prev.next; } prev.next = head; //last node connects to head var p = head; prev = null; var left = n; //number of nodes left in the list while (left >= 2) { if (left == 2) //second to last console.log("Second to last: " + prev.data); for (let i =1; i < 2; i++) { //move every other one prev = p; p = p.next; } prev.next = p.next; //remove the node from the list p = prev.next; left--; } return p.data; } let n = 5; console.log( "with " + n + " men"); let p = lastMenStanding(n); console.log("last: " + p); n = 7; console.log( "\nwith " + n + " men"); p = lastMenStanding(n); console.log("last: " + p); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class LinkNode : #Constructor, Time O(1), Space O(1) def __init__(self, value): self.data = value self.next = None #Two pointers, Time O(n), Space O(n), n is input number def lastMenStanding(n) : head = LinkNode(1) prev = head for i in range(2, n+1) : #build circular linked list, starting from 1 prev.next = LinkNode(i); prev = prev.next; prev.next = head; #last node connects to head p = head prev = None left = n #number of nodes left in the list while left >= 2: if left == 2: #second to last print("Second to last: " + str(prev.data)) for i in range (1 , 2): #move every other one prev = p p = p.next prev.next = p.next #remove the node from the list p = prev.next left -= 1 return p.data n = 5 print( "with " + str(n) + " men") p = lastMenStanding(n) print("last: " + str(p)) n = 7 print( "\nwith " + str(n) + " men") p = lastMenStanding(n) print("last: " + str(p)) |
Doodle
Output:
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)
Download LastMenStanding.java
Download LastMenStanding.js
Download LastMenStanding.py
Java Coding Interview Pocket Book
