Josephus Problem

The Josephus problem  is a problem often discussed and seen in CS literature. I got introduced to the problem when I initially started programming and knowing nothing about linked lists and/or recursion had a really hard time solving it.

The problem is stated as:
There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (are the last one remaining).

The easiest and most logical way to solve the problem is to simply simulate it using a circular link list.

N is no. of people, M as the count.

struct node {  
	int item; 
	node* next; 
};


int simple_simulation(int N, int M)
{ 
  int i;
  node *t=new node();
  node *x=t;
  t->item = 1; t->next = t;

  //Construct the list 
  for (i = 2; i <= N; i++)
  {
    x = (x->next = new node ());
    x->item = i; 
    x->next = t;
  }

  //Find the survivor
  while (x != x->next)
  {
    for (i = 1; i < M; i++) 
      x = x->next;
    x->next = x->next->next; N--;
  }
  return x->item;
}

A better way to solve the problem is through recursion. Its easy to find who is killed first, (Hint: it’s the Mth guy from the start) after that we are left with N-1 total people and the count starts from the new guy who was at M+1th position earlier. Going on like this gives us a simple recursive function:

int formula (int N, int M) 
{ 
if (N == 1)
	return 0; 
return (formula (N-1, M) + M) % N; 
}

References:

http://en.wikipedia.org/wiki/Josephus_problem