Math goodness for everyone today! We are going to be calculating the Smallest (or Least, or Lowest) Common Multiple of a range of numbers, as prompted by the Smallest Common Multiple bonfire. In mathematics, the least common multiple is the smallest positive number that is a multiple of two or more numbers (source).
As an example, take numbers 5 and 11. What is the smallest number divisible by the two? Let’s get the multiples of each and find out!
- Multiples of 5: 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65…
- Multiples of 11: 11, 22, 33, 44, 55, 66, 77, 88, 99…
As you can see, the first match we come across is number 55, that number is the least common multiple. We could try and use fancy math formulas to get it, but we are going to take advantage of our dear friend, the processor to take on the workload this time (at first). Today, I shall present you three different ways to achieve the same goal. One of them will be a more readable, short version, the second will be a little messy, but takes about half the time to come up with a solution. And the third will use some clever math and come up with the answer much faster! Interested? Let’s get to it.
We are going to get an array as input. This array will contain a finite amount of integers with a highest, and a lowest value. We must calculate the smallest common multiple of each integer in the range, for example:
smallestCommons([6, 1]); //-> Smallest common multiple of: 1, 2, 3, 4, 5, 6 smallestCommons([3, 7, 5]); //-> Smallest common multiple of: 3, 4, 5, 6, 7
For each case, we need to turn the input array into an actual range, so, for the first step, we are going to create a function that takes in an array of numbers and returns a new array containing the whole range of integers between the lowest and highest numbers in the input array. Making it simple, these are the steps that we are going to be following:
- Create a new, empty array to store the result.
- Find highest and lowest number in the input array (using reduce and the Math object).
- Loop from the lowest value to the highest and add each integer to the new array.
- Return the array.
Let’s see how it goes:
function createRange(array) {
var range = [];
var highest = array.reduce(function(a, b) {
return Math.max(a, b);
});
var lowest = array.reduce(function(a, b) {
return Math.min(a, b);
});
for (var i = lowest; i <= highest; i++) {
range.push(i);
}
return range;
}
There we go, if we input something like [4, 2], we’ll get [2, 3, 4] as output, we can work with that.
The next step will involve getting the actual smallest common multiple, this may seem a bit tricky, we need create a counter and keep incrementing it; at each iteration, we should see if said counter variable is divisible by each integer in the range array. To spice things up a bit, we are going to use the Array.prototype.every() method. This method takes a function, and passes a test to each item in the array. If any test were to fail, every() will return false. If every single value in the array passes the test, every() will return true. Every here is every a couple every examples. Sorry, I mean, Here’s two examples:
var myArray = [5, 10, 20, 100];
myArray.every(function(current) { // FALSE: 3 items do not pass the test.
return current > 30;
});
var myOtherArray = ['cats', 'dogs', 'birds'];
myOtherArray.every(function(current) { // TRUE: Every item passed the test.
return current.length > 2;
});
And that’s how it goes; so, for each counter value, if said value is divisible by every() (heh) number in the range, then, it is a common multiple. And since we’ll be incrementing the counter, the first time the test passes for the whole range, that’s where the answer is at! Sounds a bit confusing, let’s see it in action:
function smallestCommons(array) {
var range = createRange(array), // We create a range using the createRange function.
counter = 1, // Start the counter (do not start at 0, basic math!)
passed;
while (true) { // We loop until the end of time (or we return a result)
passed = range.every(function(multiple) { // If every number in the range passes, 'passed' will be true, else, it will be false.
return counter % multiple === 0; // If true, that number is a multiple.
});
if (passed) {
return counter; // If all passed, return the counter var, as it is the answer.
} else {
counter++; // If any test failed, increment the counter and start over.
}
}
function createRange(array) {
var range = [];
var highest = array.reduce(function(a, b) {
return Math.max(a, b);
});
var lowest = array.reduce(function(a, b) {
return Math.min(a, b);
});
for (var i = lowest; i <= highest; i++) {
range.push(i);
}
return range;
}
}
That’s it for the first solution! It’s not very fast, but it’s quite readable! Let’s optimize it a bit before we proceed onto the next solution. Instead of initializing the counter at 1, let’s use the highest number in the range, since no number below it can be a multiple! We are also going to get rid of the ‘passed’ variable, since we can just pass the whole thing to the if statement.
function smallestCommons(array) {
var range = createRange(array),
counter = range[range.length - 1]; // We set counter to be the last (max) value in the range.
while (true) {
if (range.every(function(multiple) { return counter % multiple === 0 })) {
return counter;
} else {
counter++;
}
}
function createRange(array) {
var range = [];
var highest = array.reduce(function(a, b) {
return Math.max(a, b);
});
var lowest = array.reduce(function(a, b) {
return Math.min(a, b);
});
for (var i = lowest; i <= highest; i++) {
range.push(i);
}
return range;
}
}
That’s a tiny bit better, we got rid of unnecessary tests and variables. Let’s go over to the second solution, make it a little faster, and in the process, messier! The range creation function remains unchanged, but instead of using every(), we are going to be using a for loop and a couple additional variables. Here’s what it looks like:
function smallestCommons(array) {
var range = createRange(array),
result = range[range.length - 1],
found = false,
counter;
while (!found) {
counter = 0;
for (var j = 0; j < range.length; j++) {
if (result % range[j] === 0) {
counter++;
}
if (counter === range.length) {
found = true;
}
}
result++;
}
return result - 1;
function createRange(array) {
var range = [];
var highest = array.reduce(function(a, b) {
return Math.max(a, b);
});
var lowest = array.reduce(function(a, b) {
return Math.min(a, b);
});
for (var i = lowest; i <= highest; i++) {
range.push(i);
}
return range;
}
}
We first create a variable to track if a result has been found or not. Then, inside a while loop, we’ll set a counter variable to 0, and loop over each item in the range. If the value in result is divisible by it, we increment the counter. If counter ever reaches the length of the range array, it means that it was divisible by every number in the range, and so, we set found to be true. If counter was lower, it means that one or more numbers didn’t pass, and so, we increment the result variable, and restart the while loop. This guy is a little messy and harder to read thorugh, but it takes about half the time to come up with the answer.
But that’s not the end of it, using some clever math formulas, we can get the answer astronomically faster. These two previous functions will struggle to get an answer for big ranges such as [1, 40], while the next solution will get it done in a flash. If you are here to get a quick solution and pass the FreeCodeCamp tests, you can ignore what comes next, if you are a little curious though, stick for a little longer!
In mathematics, the Least Common Multiple (will be calling it LCM from now on) of two integers can be obtained by means of their Greatest Common Divisor (GCD). This guy represents exactly that, the greatest divisor that both numbers have in common. The most efficient way to obtain said GCD, is by using the Euclidean algorithm. This algorithm makes use of the remainder of a division to get the GCD.
gcd(44, 6) //-> 44 % 6 = 2 -> 6 % 2 = 0 -> GCD = 2
An simple JavaScript implementation would look like so:
function gcd(a, b) {
var temp;
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
Read and walk through it as many times as need it to understand what’s happening. Now that we know how to calculate the GCD, getting the LCM is trivial:
lcm(a, b) = | a * b | / gcd(a, b) In JavaScript, we write | a * b | as Math.abs(a * b).
But now, thats just the LCM for two numbers, how do we do it with a range? Euclid comes to the rescue, following the same principal, the LCM for an array such as this [4, 6, 3] is actually: lcm(4, lcm(6, 3)). That applies for any number of items in the array. That screams of recursion, but we’ll see it work with the Array.prototype.reduce() method. First, lets implement the LCM function for two values, the same as we did for the GDC one:
function lcm(a, b) {
return Math.abs(a * b) / gcd(a, b);
}
Now, let’s apply it to an array (created using the createRange function):
function smallestCommons(array) {
var range = createRange(array);
return range.reduce(function(a, b) {
return lcm(a, b);
});
function lcm(a, b) {
return (Math.abs(a * b) / gcd(a, b));
}
function gcd(a, b) {
var temp;
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
function createRange(array) {
var range = [];
var highest = array.reduce(function(a, b) {
return Math.max(a, b);
});
var lowest = array.reduce(function(a, b) {
return Math.min(a, b);
});
for (var i = lowest; i <= highest; i++) {
range.push(i);
}
return range;
}
}
As you can see, the reduce method takes care of everything. This function is incredibly fast compared to the previous two. How fast you may be wondering, for low ranges of numbers, it doesn’t make much difference in terms of human time:
# node scm.js // -- Testing with range [1, 5] -- // Version 1: 0ms | Result: 60 Version 2: 0ms | Result: 60 Version 3: 1ms | Result: 60
Our last version even took longer! How’s is that possible! Let’s try a more challenging range:
# node scm.js // -- Testing with range [1, 13] -- // Version 1: 178ms | Result: 360360 Version 2: 75ms | Result: 360360 Version 3: 1ms | Result: 360360
Well, that’s still a very small difference from a human perspective but what happens if we increment the range a little more…
# node scm.js // -- Testing with range [1, 13] -- // Version 1: 109360ms | Result: 232792560 Version 2: 69955ms | Result: 232792560 Version 3: 0ms | Result: 232792560
That was unexpected, it took the last function less than the previous tests… That probably just my CPU being a bit faster, but look! The first function took almost 2 minutes to finish! Nonsense! I even tried doing it with the range [1, 30], and 20 30 40 minutes later, I’m still waiting for the process to finish! Guess how long it took for the third function? Yes, exactly, zero milliseconds.
You see, it made no difference to us when computing small ranges, but just taking it to a 30 number array proves to be incredibly inefficient on the first two functions. Math may not be fun for some, but it’s useful, I tell ya. Code away!
StartJS 