Josephus problem

Concrete mathematics is Eulerian mathematics.
– Concrete Mathematics, Ronald L. Graham & Donald E. Knuth & Oren Patashnik

Problem

Josephus problem is a math puzzle with a grim description: n prisoners are standing on a circle, sequentially numbered from 0 to n-1.
An executioner walks along the circle, starting from prisoner 0, removing every kth prisoner and killing him.
As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed.

Java

recurrence

1

1
2
3
4
5
6
public static int josephus(int n, int k) {
  if (n == 1)
    return 1;
  else
    return (josephus(n - 1, k) + k - 1) % n + 1;
}

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int execute(int n, int k){
    int killIdx = 0;
    ArrayList<Integer> prisoners = new ArrayList<Integer>(n);
    for(int i = 0;i < n;i++){
        prisoners.add(i);
    }
    System.out.println("Prisoners executed in order:");
    while(prisoners.size() > 1){
        killIdx = (killIdx + k - 1) % prisoners.size();
        System.out.print(prisoners.get(killIdx) + " ");
        prisoners.remove(killIdx);
    }
    System.out.println();
    return prisoners.get(0);
}

circular linked list

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
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.printf("Last person left standing (Josephus Position) is %d \n", ptr1.data);
}

ref