A Thinking Ape - Algorithm Solution

This challenge consists of solving the classic Josephus problem.

The problem has a game like approach of removing people from a circle in constant intervals and the winner is the last one left from the original circle. The idea is to know beforehand where to stand in the circle as to ensure you are the last one removed and thus the winner.

It is basically a circular list. Since people stay in such a way as to form a circle and the leap count interval is fixed, no matter how many people you skip you can always predict who will be the last to be eliminated.

Take a simple example where you have 7 people forming a circle (n=7) and you remove every other person (k=2).

Your starting group would look something like that: [1,2,3,4,5,6,7]

The game starts at member 1 and the count goes on skipping every other member of the circle.

So, on the first round, numbers 2, 4 and 6 would be eliminated.

On the second round, numbers 1 and 5 would be eliminated.

And lastly, number 3 would be eliminated, resulting in a winner number 7.

The game is pretty much recursive. Since it is circular, as the list gets shortened, it iterates over it again and again.

So, whenever a person is eliminated from the circle, “n” receives a new value of “n-1”.

n = n - 1

However, “k” (the skip value) remains the same, resulting in the following solution: ( f ( n – 1 , k ) + k ) % n

Built With

• logic