Solving the Josephus problem in JavaScript

We will survive!

Trung Anh Dang
Mar 25 · 3 min read
Photo by Artem Maltsev on Unsplash

What is the Josephus Problem?

In computer science and mathematics, the Josephus Problem is a theoretical problem.

Following is the problem statement:

There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. 

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

The origin of the story

There are 9 Jewish hid in a hole with Josephus and his friends. The 9 Jews decided to die rather than be caught by the enemy, so they decided In a suicide method, 11 people are arranged in a circle, and the first person reports the number. After each number is reported to the third person, the person must commit suicide. Then count again from the next one until everyone commits suicide.
But Josephus and his friends did not want to obey. Josephus asked his friends to pretend to obey, and he arranged the friends with himself. In the 2nd and 7th positions, they escaped this death game.

How will we solve it in JavaScript?

In general, the classic Josephus problem has two parameters: N and K. A circle of N people is formed, and successively every K-th person is selected for elimination. As people are killed off, the circle shrinks, and the goal is to determine last surviving position.

We can solve the Josephus problem for a collection of N elements using an array. The array is treated as a ring.

First, we define an array of positions — m (N elements), initialize a value of 0.

var man = new Array()
for (var i = 0; i < N; i++)
man[i] = 0

Next, we determine the position of killed person — value of the pos variable.

do {
pos = (pos + 1) % N // Ring
if (man[pos] == 0)
i++
if (i == K) {
i = 0
break
}
} while (true)

Then, we update the killed person in m array and go to the next turn.

man[pos] = count
count++

We continue the loop until we reach N. Finally, here is our full solution.

const joseph = function (N, M) {
var man = new Array()
for (var i = 0; i < N; i++)
man[i] = 0
var count = 1
var i = 0, pos = - 1
while (count <= N) {
do {
pos = (pos + 1) % N // Ring
if (man[pos] == 0)
i++
if (i == K) {
i = 0
break
}
} while (true)
man[pos] = count
count++
}
return man
}

Try to test this solution.

var game = Joseph (11, 3)

With N = 20, M = 3. In the 13th or 20th positions, you will escape this death game.

var game = Joseph (20, 3)

Easy, right?


Thanks for reading 😘, goodbye 👋, and don’t forget to 👏 up to 50 times and follow!

JavaScript in Plain English

Learn the web's most important programming language.

Thanks to Sunil Sandhu

Trung Anh Dang

Written by

I write about things that I like and things that I don’t, mainly in the business, art and tech sphere

JavaScript in Plain English

Learn the web's most important programming language.

More From Medium

More from JavaScript in Plain English

More from JavaScript in Plain English

More from JavaScript in Plain English

32 funny Code Comments that people actually wrote

10.3K

More from JavaScript in Plain English

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