Russian roulette

This is a specific example of the Josephus problem whereby given a ring of \(n\) people, starting at position \(p\), every \(k\)-th person is eliminated. For this challenge, we define \(k = 2\) (since every second person is eliminated).

As with any problem, it helps to establish the solutions for some small values of \(n\) before generalising.

It may not be immediately apparent, but we observe an interesting pattern: the sequence of \(f(n)\) is equal to the sequence of odd numbers, which restarts whenever \(n\) is a power of \(2\). This is because the next odd number in the sequence would have produced \(f(n) > n\), leading to an invalid solution.

Consider that given the constraint \(k = 2\), meaning that every second person is eliminated, the first pass will always eliminate every even position. For example, if we take a circle of \(n = 6\) people, we eliminate \(2, 4, 6\) in the first pass, then \(3\) in the next pass, then \(1\) in the last pass, leaving the person in position \(5\) as the sole survivor. Increasing to \(n = 7\), we find that in the first pass positions \(2, 4, 6\) are still eliminated, followed by \(1, 5\) in the second pass, then \(3\) in the third pass, leaving the person in position \(7\). This means \(f(n)\) is always guaranteed to be an odd number.

From here, note that all odd numbers are of the form \(2x + 1 \space \forall \space x \in \mathbb{Z}\). Since the sequence of all positive odd numbers can be obtained by constraining \(x \geq 0\), and the sequence of \(f(n)\) resets to the base case of \(x = 0\) at every power of \(2\), \(x\) must be equal to the difference between \(n\) and the previous power of \(2\). In other words, \(x\) is the difference between \(n\) and the largest power of \(2\) which does not exceed \(n\). Therefore we can define \(x\) as:

Substituting this into the \(2x + 1\) form for odd numbers, we find the following solution:

This solution can be implemented in C# like so:

int LastSurvivor(int n)
{
	int previousPower = (int)Math.Pow(2, (int)Math.Log2(n));
	int x = n - previousPower;
	return 2 * x + 1;
}

However there exists a far more efficient solution. There's some use of \(2^x\) and \(\log_2\) which strongly indicates a solution may exist by manipulating the binary representation of \(n\).

First, note that expressing \(2^x\) for any positive integer \(x\) is equivalent to setting a \(1\) bit in the \(x\) position of the binary representation. For example \(8\) - or \(2^3\) - in binary is \(1000_2\). This is equivalent to the expression 1 << 3 - simply shifting the \(1\) bit \(x\) places to the left.

This means we can remove the Pow call and change the function to the following:

int LastSurvivor(int n)
{
	int previousPower = <mark>1 << (int)Math.Log2(n);</mark>
	int x = n - previousPower;
	return 2 * x + 1;
}

Next, we note that multiplying a number by \(2\) is equivalent to a left shift of \(1\). i.e. 2 * x == x << 1. This leaves us with the following:

int LastSurvivor(int n)
{
	int previousPower = 1 << (int)Math.Log2(n);
	int x = n - previousPower;
	return <mark>(x << 1)</mark> + 1;
}

Lastly, we can take a more efficient approach to computing the logarithm. .NET 7 introduced the BitOperations.Log2 method which:

This is exactly what we're already doing by casting the result of Math.Log to int, so we can swap that out - making sure to cast \(n\) to uint as this method only accepts unsigned values:

int LastSurvivor(int n)
{
	int previousPower = 1 << <mark>BitOperations.Log2((uint)n)</mark>;
	int x = n - previousPower;
	return (x << 1) + 1;
}

We can replace the addition of \(1\) with the logical OR of \(1\). In this case, these operations are identical as a left shift of \(x\) is always going to leave the LSB at \(0\). A carry will not occur here.

int LastSurvivor(int n)
{
	int previousPower = 1 << BitOperations.Log2((uint)n);
	int x = n - previousPower;
	return (x << 1) <mark>|</mark> 1;
}

You may start to see what's happening here. previousPower is equal to a value where only the MSB of \(n\) is \(1\) and the rest of the bits are \(0\). For example if \(n\) is equal to \(10110_2 = 22\), then previousPower is equal to \(10000_2 = 16\). We're just finding the largest power of two that doesn't exceed \(n\). Then we subtract this from the original \(n\) value for \(x\), leaving us all digits except the MSB. If \(n\) is equal to \(10110_2 = 22\), then \(x\) is equal to \(110_{2} = 6\).

Next, we're shifting left by \(1\) (equivalent to multiplying by \(2\)), giving us \(1100_{2} = 12\). Lastly we add/OR \(1\) just as before, giving us a final result of \(1101_{2} = 13\).

Do you see it? You'd be forgiven for missing it. Take a look at the binary representations of the input and the output:

This is a cyclic left shift! Also known as a “bitwise rotate”, the MSB of the input (which will always be \(1\) according to our logic) is simply taken and placed at the end of the original input.

Isn't that cool?

We could actually one-line this entire operation like so:

int LastSurvivor(int n)
{
	return ~(1 << BitOperations.Log2((uint)n) << 1) & ((n << 1) | 1);
}

To implement the bonus challenge, where we also accept a starting position \(p\), all this really requires is shifting the positions cyclically:

Implementing this in code is an exercise I leave to you, the reader.