Algorithms as Data Structures: a Study of the Josephus Problem

Allen Woods
Nov 5 · 4 min read

A popular take on programming is that the fastest code you can write is no code at all. Leaner code is by definition more efficient, but focusing purely on the amount of syntax can easily miss the structures within that syntax; namely, the data structures being used.

What you are writing is just as important as how much you’re writing. One good example that demonstrates these concepts brilliantly is the Josephus Problem. The problem is named after Josephus, a Biblical figure who found himself surrounded by the Romans along with a host of Jewish soldiers.

The loose synopsis goes that the soldiers preferred death to being captured, so they decided to stand in a circle where every other man would kill the soldier to his left until only one remained. Josephus, who was rather partial to being alive and wanted to stay that way, set about calculating where to stand in the circle so that he would be the lone survivor.


At its simplest, the object of solving the Josephus Problem is to solve for the lone survivor within a group of “n” people.

To be more specific, it involves a process of elimination wherein every odd member of the group of living participants kills the next adjacent person to the left in an alternating pattern, starting with person one.

This process sounds a bit involved, and it can be. An excellent blog post by Amando Abreu details how to programmatically perform this calculation at length, which can be read here:

If we take a look at an excerpt of the code provided, we can see that Amando’s solution provides a means for keeping track of the state of each participant within the overall process of elimination:

var kill = function(arr){
if (arr.length < 2){
// This is our last soldier alive.
return arr;
}
var survivors = arr.filter((soldier, index) => index % 2 == 0); if (arr.length % 2 !== 0){
// Add the last person the start
// if the number of people is odd.
survivors.unshift(survivors.pop());
}
return kill(survivors);
}

This is a sensible solution to the problem, but what if we only need the final answer in the shortest amount of time and the fewest number of steps?


A lot of emphasis is rightly given to the importance of understanding code, but it’s also important to maintain diversity in the resources you pull your information from. Some aspects of becoming a better programmer, such as the ones mentioned here, can’t always be discovered easily within the monolithic universe of exploring stacks and codebases. Sometimes seemingly unrelated content on YouTube can offer better answers.

The Josephus Problem has been covered on Numberphile, an excellent maths-related YouTube channel. In their coverage, a very curious and advantageous property of the maths involved in this specific problem was brought to my attention.

The answer to this problem can be calculated by converting the number of people participating into binary, then moving the left-most bit into the one’s place on the right-hand side. The integer represented by the new binary string will always be the solution to the problem.

Knowing this, we can leverage data structures within Number and String to greatly reduce the amount of code we write, as follows:

const josephus = (n) => {
/*
* If we have received a valid number, convert it
* to a binary string using a radix of 2.
* Move the left-most bit to the one's place.
* Return the integer equivalent.
*/
if (n && !isNaN(n) && n > 0) {
let bin = (n).toString(2)
let survivor = bin.slice(1) + bin.charAt(0)
return parseInt(survivor, 2)
}
}

The above code will achieve the same final result as the solution written by Amando in his more in-depth article, but the execution time and quantity of code is much reduced.

There are many ways to achieve the same result, which is what makes programming so fun, expressive, and individuated. Developing the knowledge of not only how to write a solution, but what to write (and how much) is an endless skill tree that will be continuously built in the course of our careers.

A couple tricks you can try to boost your skills are using applied mathematics to guide you in leveraging the structures embedded within the data itself. Even big things can have small solutions.

Thanks for reading, and I hope this has helped you see the patterns you might otherwise miss.

If you like the message in this article, I write blogs focusing on the more nuanced aspects of programming, including implementations of mathematical concepts.

To have a look at Numberphile’s excellent video on this topic, you can check it out below:

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