Josephus Problem

LastSurvivor.java

/*******************************************************
Program Number: A2_1
Purpose/Description: Deletes every kth element in a circular array until 
there is only 1 element left standing.
Author: Alastair Paragas
Due date: 10/02/2015
Certification:
I hereby certify that this work is my own and none of it is the work of
any other person.
    Alastair Paragas
*******************************************************/

package assignment2.problem1;


public class LastSurvivor {
    
    /**
     * Deletes every kth element in a circular array until there is only 1 
     * element left standing.
     * @param arr - Array that contains n items, numbered from 1 to n
     * @param n - Amount of items
     * @param k - Multiples of item numbers to remove from the given array
     * @return Survivor's position in the initial array
     */
    public int lastsurvivor(int arr[], int n, int k) {
        
        // If there is only a population with a size of 1
        // the element that would be killed (but due to the constraints of the
        // game, left to survive), would be at the "0" position of the array.
        if (n == 1) {
            return arr[0];
        }
        
        // Modulus allows us to circulate arround the array
        // Modulus of population size allows us to circulate around the array
        // The person killed at a round is k units away from the person killed 
        // at a previous round. Since the population size decreases by 1, the 
        // new distance of the person to be killed from the previous person 
        // killed (and removed from the population), is k-1 distance units away.
        return arr[(k - 1 + lastsurvivor(arr, n - 1, k)) % n];
        
    }
    
}