Josephus Problem Algorithm

Josephus Problem is a theoretical Counting Game Problem.
n people stand in a circle and are numbered from 1 to n in clockwise direction.
Starting from 1 in clockwise direction each person kills the k^th person next to him and this continues till a single person is left. The task is to choose a suitable position in initial circle to avoid execution.

Explanation

Image credits: (Exploring Binary)

Recurrence Relation

J(1,k) = 1

J(n,k) = (J(n-1,k) + k-1 ) mod n +1

Complexity

Time complexity = O(n)

---

<p align="center"> A massive collaborative effort by <a href="https://github.com/OpenGenus/cosmos">OpenGenus Foundation</a> </p>

---