Josephus Problem

The Josephus problem has existed for a long time, and its solutions have continually improved. However, no extremely efficient algorithm (within log complexity) is currently known.

Problem statement

n people numbered $0,1,\cdots, n-1$ stand in a circle counterclockwise. Starting from person $0$, count $k$ people counterclockwise from the current person each time, and remove the person reached. Who is the last person remaining?

This classic problem was posed by Josephus in the first century CE, although he considered only the case $k=2$. Today, many efficient algorithms can solve it.

Process

Naive algorithm

The most naive algorithm is direct enumeration. Use a circular linked list to simulate the deletion process, repeating it $n-1$ times to obtain the answer. The complexity is $\Theta (n^2)$.

Simple optimization

The process of finding the next person can be optimized with a segment tree. Build a segment tree over $0,1,\cdots, n-1$ and record the number of people remaining in each interval. The current person's position and the position of the $k$-th person after them can be found by binary search on the segment tree.

Linear algorithm

Let $J_{n,k}$ denote the answer to the Josephus problem with parameters $n,k$. We have the recurrence

This is easy to derive. Starting from $0$, count $k$ people and remove person $k-1$. After the remaining $n-1$ people are solved, calculate the answer among the remaining $n-1$ people, then add a relative offset of $k$ to obtain the actual answer. The complexity is clearly $\Theta (n)$.

int josephus(int n, int k) {
  int res = 0;
  for (int i = 1; i <= n; ++i) res = (res + k) % i;
  return res;
}

Logarithmic algorithm

When $k$ is small and $n$ is large, there is also an algorithm with complexity $\Theta (k\log n)$.

Since we delete one person after every $k$ steps, within one full circle we can delete $\left\lfloor\frac{n}{k}\right\rfloor$ people, leaving $n-\left\lfloor\frac{n}{k}\right\rfloor$ people. We are then at the position of person $\left\lfloor\frac{n}{k}\right\rfloor\cdot k$, which equals $n-n\bmod k$. We continue recursively and restore the relative position afterward. The reason for restoring the position is that every deletion removes the $k$-th person counted, and the people after them inherit their numbers one by one. Thus, when counting around a circle of $n-\left\lfloor\frac{n}{k}\right\rfloor$ people, one position is miscounted for every $k$ people. If the result is less than $0$, take it modulo $n$ in the circle of $n$ people whose multiples of $k$ have not yet been deleted; if the result is greater than or equal to $0$, there is $1$ miscounted position for every group of k people, so it can be multiplied directly by $\frac{k}{k-1}$. This gives the following algorithm:

int josephus(int n, int k) {
  if (n == 1) return 0;
  if (k == 1) return n - 1;
  if (k > n) return (josephus(n - 1, k) + k) % n;  // Linear algorithm
  int res = josephus(n - n / k, k);
  res -= n % k;
  if (res < 0)
    res += n;  // mod n
  else
    res += res / (k - 1);  // Restore the position
  return res;
}

It can be proved that this algorithm has complexity $\Theta (k\log n)$. Let $x$ be the number of recursive calls. At each step, the problem size becomes approximately $\displaystyle n\left(1-\frac{1}{k}\right)$, so

Solving this equation gives

We now prove that the complexity is $\Theta (k\log n)$.

This page is mainly translated from the blog post Задача Иосифа and its English translation Josephus Problem. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.