An explanation on Josephus problem aka Suicide Circle problem

Jan 1, 2018 · 2 min read
Flavius Josephus

Josephus problem is one of the numberphile in Computer Science. It is also called as suicide circle problem because of the history behind it.

Flavius Josephus, a Jewish soldier, and historian lived in the first century. He fought along with 39 soldiers against Roman in a war, where they have trapped in a cave. The soldiers except Josephus decided to take their lives instead of getting killed by the Romans. So they formed a circle known as suicide circle. Each person standing on the circle should kill the person next to them and hand over the weapon to next living soldier. Till the last survivor, the game should go on.

Josephus decided to live and found a way to escape from the suicide circle. He calculated the position which other soldiers cannot kill. He himself placed in 17th position and escaped from the suicide circle.

The Actual Josephus problem

In a circle where n people stand and k is the skipping interval, find which position will come last. The problem is taken based on the 1-index people standing on top of it.

Let’s say a circle made up of 4 people and the skipping interval is 2. Keep in mind, it is 1-index and interval starts from the active index.

At first,

1* 2 3 4

The number 1 will count off number 2 and 3 will become active.

1 x 3 * 4

Number 4 will count off from the circle and number 1 will become active,

1* x 3 x

Number 3 will count off, then 1 will become active and the last survivor of the game.

1* x x x

In each iteration n will be reduced by 1, i.e., n will become n-1 and the indices will change respectively.

There is already a solution available based on dynamic programming, the following equation derived to solve this problem.

f(n,k) = ((( f(n-1), k ) + k -1 ) % n) +1, where f(1, k) = 1.

Shall we substitute the values of our problem?

Lets take n = 4 and k = 2 for simplicity, so the equation would become

f(4,2) = ((( f(4–1), 2 ) + 2 -1 ) % 4) +1

to solve we need f( 3, 2 )

f(3,2) = ((( f(3–1), 2 ) + 2 -1 ) % 3) +1

to solve this we need f( 2, 2 ),

f(2,2) = ((( f(2–1), 2 ) + 2 -1 ) % 2) +1

we know that, f(1,k) = 1 hence f(1,2)=1. Now substitute the values

f(2,2) = 1

f(3,2) = 3

f(4,2) = 1

Hence the survivor is number 1.

Below is the C# implementation of the same.

Originally published in Trendy Tech News.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade