Hi Everyone! I was working on a FreeCodeCamp algorithm challenge the other day and kept running into timeout issues when I ran it in their editor. I had tried it elsewhere and it was working, but I figured that I needed to optimize the solution so that it would run on FreeCodeCamp’s servers. After spending quite a bit of time working on how to get the smallest common multiple, I think I’ve arrived at a really performant solution, so I wanted to share it with you all here.
If you’d like to try it out for yourself, the challenge is called Smallest Common Multiple on FreeCodeCamp’s website. The instructions say that we’re going to have a function called
smallestCommons that will take a single parameter
arr. Our parameter
arr is an array with two elements in it (
[1,5]) and we're told that they may not be in numerical order. The task we're given is to find the smallest common multiple of the provided numbers (in
arr) that can be evenly divided by both, as well as by all of the sequential numbers in the range between the two numbers.
For example, for
smallestCommons([1,5]) we'd need to return the smallest number that is evenly divisible by 1, 2, 3, 4 & 5. The test cases we're given are as follows:
Splitting the problem into Pieces
So my goal here was to split the problem into pieces. The main way I did that here was by defining a few functions to handle parts of the problem.
First, I added a
getRange function that takes in the same
arr we're given from our test cases and outputs the range of numbers that we're going to check for even divisibility.
When I was first approaching this problem I ended up running into issues with timeouts because I had a giant loop going on. So another goal I had was to reduce the amount of looping I had to do by as much as possible. One of the ways I’ve tried to do that is by adding
return statements within the loops, so that we break out of them the moment we know what we need to know. I've also implemented a closure to create a factorial function generator that keeps track of the math it has already done so it only has to do the work once. This is particularly handy for a factorial function because it means that once you call
factorial(100), all of the return values for
factorial(2)... all the way to
factorial(99) are already stored in memory.
This factorialFactory function will be used to calculate the upperLimit of the values that we’ll be checking for common multiplicity.
Finally, this function will take in a
range of numbers and check to see if
num is a common multiple of each of the numbers in the range. Because I was having issues with performance before, this function is designed to only check all of the numbers in the range if the
num we pass in is an even multiple of all of the top n-1 numbers in the range.
Putting the pieces together in smallestCommons(arr)
Now that we’ve got the problem split into those subtasks, we can go about implementing the solution. In my solution, I’m using the factorialFactory to calculate the upperLimit of the values I need to check for common multiplicity. The largest possible value for the Smallest Common Multiple is the product of all of the numbers in the range. This also happens to be equivalent to the factorial of the larger number divided by the factorial of one less than the smaller number. For example, if we had a range of:
[5,6,7,8,9] the product
5*6*7*8*9 is equivalent to
After we’ve gotten our
upperLimit defined, we can use a for loop to find our smallest common multiple. Our first time through the loop, the counter i will be set equal to the
largestNum value. The loop will continue until the counter is no longer less than our
upperLimit. And after each iteration, the counter will be incremented by largestNum. Essentially, what we're doing here is looping through the multiples of the largest number in our range and checking each one to see if it's a common multiple of each number in the range. Once we find our first match we'll return it. If we don't find a match, we'll return the
upperLimit value, which is the product of all of the numbers in the range.
Here’s the final algorithm code for your reference:
I’ve really enjoyed working through Algorithm challenges on FreeCodeCamp, CoderByte and HackerRank. More recently, I’ve also really enjoyed doing some challenges on codefights as well!
Originally published at Becoming a Programmer.