Question

Assume N people have decided to elect a leader by arranging themselves in a circle and eliminating every Mth person around the circle, closing ranks as each person drops out. Find which person will be the last one remaining (with rank 1). HINT: Assume the input is a circular linked list with N nodes and each node has a number (range 1 to N) associated with it. The head node has number 1 as data. Although. It will be easier to implement the solution using a circular linked list, you are free to use Array if you see appropriate.

Answer 1

The problem has following recursive structure.

  josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1
  josephus(1, k) = 1

After the first person (kth from beginning) is dropped out, n-1 persons are left. So we call josephus(n – 1, k) to get the position with n-1 persons.

Here is the pseudocode to do the same

PSEUDOCODE

int josephus(int N, int M)

{

  if (N == 1)

    return 1;

  else

    return (josephus(N - 1, M) + M-1) % N + 1;

}

CODE

public class Main {

public static class Node

{

public int data ;

public Node next;

public Node( int data )

{

this.data = data;

}

}

public static void getJosephusPosition(int m, int n)

{

Node head = new Node(1);

Node prev = head;

for(int i = 2; i <= n; i++)

{

prev.next = new Node(i);

prev = prev.next;

}

prev.next = head;

Node ptr1 = head, ptr2 = head;

while(ptr1.next != ptr1)

{

int count = 1;

while(count != m)

{

ptr2 = ptr1;

ptr1 = ptr1.next;

count++;

}

ptr2.next = ptr1.next;

ptr1 = ptr2.next;

}

System.out.println("Elected position = " + ptr1.data);

}

public static void main(String args[])

{

int n = 20, m = 3;

getJosephusPosition(m, n);

}

}