Puzzle: Who wins the game?

Question

A group of children form a ring. The first child is selected and they start counting clockwise from that child until a fixed number (n, which is given at the starting of the game) is reached. When the count reaches n, the child on the nth spot is eliminated. The game continues again starting with the next child and the process continues until a single child remains.Your aim is to print the position of the child which remains till last.

For example, if there are 10 children and the fixed number n is 6, the position of the last child who remains till the last is 3.

Is there a better programmatic algorithm for solving this problem?

P.S. I know that we can easily do this using arrays or other data structures. I just want the best strategy, preferably a mathematical approach.

Answer 1

I think the easiest way is still write a recurrence (pretty much what wikipedia says, give upvotes to Jan Dvorak):

T(1) = 0
T(c) = (T(c-1)+n) mod c

Or, writing as C (with no recursion):

int non_fatal_josephus(int children, int n) {
    int result = 0;
    for(int i=2; i<=children; i++)
        result = (result + n) % i;

    return result + 1; //to make it one-based
}

Recurrence explanation:

T(c) means "which child will win if we start with c children".

T(1) = 0 because if we have only 1 children, she already won (the 1st child, index 0).

The general case is that we always eliminate the nth children (index n-1), as soon we eliminate her, we start counting again with (c-1) children, but this time, instead of starting at index 0, we start at index n. That explains the +n: T(c-1) assumes the counting starts at 0. We use the +n to shift the child index as if we started at index n.