Some guys holding swords are playing a game. This game will be the last one for most of them.
The rules of the game are the following: the players are standing in a circle. Person number 1 starts the game by killing the guy to the left of him. After that, the next living person to his left kills his the closest person to their left of him who is still alive. The game continues until there's only one person left.
Your task is, given the number of players playing the game, to find the last survivor and return the one-based position of that person. Assume that the person who starts the game has number 1, and the players are enumerated in the clockwise direction.
Example
For n = 10, the output should be
onlySurviver(n) = 5.
Here's why:
 |
|
Input/Output
- [time limit] 4000ms (js)
[input] integer players
Constraints:
0 < players < 231.[output] integer
1-based position of the survivor of the game.
Solution
This problem is known as the Josephus problem and can be solved recursively. However, we'll work out a closed form solution here, similar to the one on Wikipedia.
Let \(f(n)\) denote the position of the last man standing with the initial number \(n\) of people in the circle. When we go around the circle for the first time, all even-numbered people die. For the second round, it depends on if the initial number was even or odd. If it was even, it starts all over with 1 kills 3 and so on. If the number was odd, the last person will kill 1 and so on. We can continue this until only one person remains.
If the initial number of people was even, the person at position \(p\) was previously in position \(2p-1\). Let \(n=2k\), the person at \(f(k)\) who will now survive was originally in position \(2f(k)-1\), which gives the recurrence
\[f(2k)=2f(k)-1.\]
If the initial number of people was odd, the person at position \(p\) was previously in position \(2p+1\). Let \(n=2k+1\), the person at \(f(k)\) who will now survive was originally in position \(2f(k)+1\), which gives the recurrence
\[f(2k+1)=2f(k)+1.\]
Looking at the function values for the first 20 numbers, we see a pattern emerge:
For every \(f(n)=1\), the number of people was a power of two. If we choose \(m\) and \(l\) such that \(n=2^m+l\) with \(0\leq l< 2^m\), it follows that \(f(n)=2l+1\). We can think about it, that after \(l\) people are dead there are only \(2^m\) people and we go to the \(2l+1\text{th}\) person. He must be the survivor, so \(f(n)=2l+1\).
In an implementation using integers, the highest bit denotes \(2^m\) and the remaining bits will be \(l\). That means, that we simply need to remove the highest set bit. The most significant bit can be calculated with the integer log base two Math.log2(n) or with ES6 arrival 31-Math.clz32(n). A straightforward implementation is then
function onlySurviver(n) {
var l = n - Math.pow(2, Math.log2(n) | 0);
return 2 * l + 1;
}
Since the task requires to minimize the code, we'll stick with Math.log2 and try to reduce the size of the solution as much as possible. The first step is to remove the explicit function declaration and Math.pow, since they cost a lot of bytes:
onlySurviver = n =>
2 * (n - (1 << Math.log2(n))) + 1
Since we know that \(n\) has set the bit at the most significant bit, we can use xor, to toggle the bit:
onlySurviver = n =>
2 * (n ^ 1 << Math.log2(n)) + 1
The multiplication of two is totally unnecessary, since it's a simple left shift and can be accomplished with the shift we already have:
onlySurviver = n =>
(2 * n ^ 2 << Math.log2(n)) + 1
It's already pretty small. However, what happens if I binary negate a number and negate it back? It's the same number obviously. What happens if I negate a number binary and negate it in two's complement? One is added! That means we can rewrite the function again:
onlySurviver = n =>
-~(2 * n ^ 2 << Math.log2(n))
We haven't saved anything by now, but we can abuse the operator priority of ~ to get rid of the multiplication entirely, as well as the brackets:
onlySurviver = n =>
n - ~n ^ 2 << Math.log2(n)