# Solving the Josephus problem in JavaScript

## We will survive!

# 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)<< [ 4,10, 1, 7, 5, 2,11, 9, 3, 6, 8 ]

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

var game = Joseph (20, 3)[ 7, 18, 1, 12, 8, 2, 15, 17, 3, 9, 13, 4,19, 10, 5, 16, 14, 6, 11,20]

Easy, right?

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