Skip to content

Josephus Problem

The Josephus problem has a long history, and its solutions have been continuously improved, though there is still no extremely efficient algorithm (logarithmic or better) to solve it.

Problem Description

There are \(n\) people labeled \(0,1,\cdots, n-1\). They stand in a circle counter‑clockwise, starting from person \(0\). Each time we count \(k\) people counter‑clockwise from the current person, and that person leaves the circle. Determine the label of the last remaining person.

This classic problem was proposed by Josephus in the 1st century, although he only considered the case \(k=2\). Nowadays we can solve it with many efficient algorithms.

Solutions

Naïve Algorithm

The most straightforward algorithm is to simulate the process directly. Use a circular linked list to repeatedly delete the \(k\)-th person, repeating \(n-1\) times to obtain the answer. Complexity \(\Theta(n^2)\).

Simple Optimization

The process of finding the next person can be accelerated with a segment tree. Specifically, build a segment tree over \(0,1,\cdots, n-1\) that maintains the count of remaining people in each interval. Finding the current position and the \(k\)-th person after it can be done with binary search on the segment tree.

Linear Algorithm

Let \(J_{n,k}\) denote the answer to the Josephus problem with parameters \(n\) and \(k\). We have the recurrence

\[ J_{n,k}=(J_{n-1,k}+k)\bmod n \]

This is easy to derive: starting from \(0\), we count \(k\) people, remove the \((k-1)\)-th person, leaving \(n-1\) people. After computing the answer for \(n-1\) people, we add an offset \(k\) to obtain the real answer. The complexity of this algorithm is clearly \(\Theta(n)\).

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

Logarithmic Algorithm

For the case where \(k\) is small and \(n\) is large, there exists an algorithm with complexity \(\Theta(k\log n)\).

Observe that each time we skip \(k\) people and delete one, so within one full round we can delete \(\left\lfloor\frac{n}{k}\right\rfloor\) people, leaving \(n-\left\lfloor\frac{n}{k}\right\rfloor\) people. At this point we are at position \(\left\lfloor\frac{n}{k}\right\rfloor\cdot k\), which equals \(n - n \bmod k\). Then we recursively solve the smaller problem and afterwards restore the relative position. The restoration is based on the fact that each deletion removes every \(k\)-th person, and the labels of the remaining people shift accordingly. In the reduced circle of size \(n-\left\lfloor\frac{n}{k}\right\rfloor\), every \(k\)-th position corresponds to a deleted person in the original circle. Therefore, if the computed result is negative, we adjust it modulo \(n\); otherwise we multiply by \(\frac{k}{k-1}\). This leads to the following algorithm:

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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 position
  return res;
}

It can be proved that the complexity of this algorithm is \(\Theta(k\log n)\). Let \(x\) be the number of recursive calls. Each time the problem size reduces roughly to \(\displaystyle n\left(1-\frac{1}{k}\right)\), so we have

\[ n\left(1-\frac{1}{k}\right)^x=1 \]

Solving this equation gives

\[ x=-\frac{\ln n}{\ln\left(1-\frac{1}{k}\right)} \]

Now we prove that the complexity is \(\Theta(k\log n)\).

Proof

Consider \(\displaystyle \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right)\). We have

\[ \begin{aligned} \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right)&=\lim _{k \rightarrow \infty} \frac{\log \left(1-\frac{1}{k}\right)}{1 / k}\\ &=\lim _{k \rightarrow \infty} \frac{\frac{\mathrm d}{\mathrm d k} \log \left(1-\frac{1}{k}\right)}{\frac{\mathrm d}{\mathrm d k}\left(\frac{1}{k}\right)}\\ &=\lim _{k \rightarrow \infty} \frac{\frac{1}{k^{2}\left(1-\frac{1}{k}\right)}}{-\frac{1}{k^{2}}}\\ &=\lim _{k \rightarrow \infty}-\frac{k}{k-1}\\ &=-\lim _{k \rightarrow \infty} \frac{1}{1-\frac{1}{k}}\\ &=-1 \end{aligned} \]

Hence \(x \sim k \ln n\) as \(k\to \infty\), i.e., \(-\dfrac{\ln n}{\ln\left(1-\frac{1}{k}\right)}= \Theta (k\log n)\).

This page is mainly translated from the blog Task Josephus and its English translation Josephus Problem. The Russian version license is Public Domain + Leave a Link; the English version license is CC-BY-SA 4.0.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用