Josephus.java

/*************************************************************************
 *  Compilation:  javac Josephus.java
 *  Execution:    java Josephus M N
 *  
 *  Given N people indexed 1 through N in a circle, suppose every Mth one
 *  is eliminated, starting from person 1. Print out the order in which
 *  people are eliminated. Uses a circular linked list.
 *
 * 
 *  % java Josephus 5 9
 *  5 1 7 4 3 6 9 2 
 *  Survivor is 8
 *
 *************************************************************************/

public class Josephus { 

    private static class Node {
       int value;
       Node next;
    }

    // create a circular linked list of 1..N and return reference to last node
    public static Node create(int N) {
        Node last  = new Node();
        Node first = last;
        last.value = N;

        for (int i = N-1; i >= 1; i--) {
            Node x  = new Node();
            x.value = i;
            x.next  = first;
            first   = x;
        }
        last.next = first;
        return last;
    }

    // count number of nodes in a circular linked list
    public static int count(Node first) {
       int n = 0;
       Node x = first;
       do {
          x = x.next;
          n++;
       } while (x != first);
       return n;
    }


    public static void main(String[] args) {
        int M = Integer.parseInt(args[0]);      // eliminate every Mth person
        int N = Integer.parseInt(args[1]);      // number of people

        Node x = create(N);
        System.out.println("count = " + count(x));

        // delete every Mth person
        while (x != x.next) {

            // skip M-1 positions         
            for (int i = 1; i < M; i++)
                x = x.next;
            System.out.print(x.next.value + " ");

            // kill the Mth one
            x.next = x.next.next;
        }

        // print survivor
        System.out.println();
        System.out.println("Survivor is " + x.value);
    }
}