Puzzle: Who wins the game?

Question

A group of children form a ring. The first child is selected, and they start counting clockwise from this child until a fixed number is reached (n, which is given at the beginning of the game). When the counter reaches n, the child in the nth place will be deleted. The game continues again, starting with the next child, and the process continues until there is only one child left. Your goal is to print the position of the child who remains to the last.

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

Is there a better software algorithm to solve this problem?

PS I know that we can easily do this with arrays or other data structures. I just need a better strategy, preferably a mathematical approach.

Answer 1

I think the easiest way is still to write the repetition (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 (without 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 } 

Repetition Explanation:

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

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

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