# Get Smallest Common Multiple with JavaScript

Algorithm Challenges

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:

```smallestCommons([1,5]) should return a number.
smallestCommons([1,5]) should return 60.
smallestCommons([5,1]) should return 60.
smallestCommons([1,13]) should return 360360.
smallestCommons([23,18]) should return 6056820.
```

## 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.

#### getRange(arr)

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.

```function getRange(arr) {
var range = [];
for (var i = arr.sort() ; i <= arr.sort() ; i++) {
range.push(i);
}
return range;
}

getRange([1,5]); // => [1,2,3,4,5]
getRange([5,1]); // => [1,2,3,4,5]
```

#### factorialFactory()

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(1)`, `factorial(2)`… all the way to `factorial(99)` are already stored in memory.

```function factorialFactory() {
var memo = {};

function factorialFunc(num) {
if (memo.hasOwnProperty(num)) {
console.log(memo[num] + " (from memory)");
return memo[num];
} else {
var factorial = 1;
for (var i = 1; i <= num ; i++) {
factorial *= i;
memo[i] = factorial;
}
console.log(factorial + " (computed)");
return factorial;
}
}

return factorialFunc;
}

var factorial = factorialFactory();

factorial(10); // 3628800 (computed)
factorial(9);  // 362880 (from memory)
factorial(8);  // 40320 (from memory)
```

This factorialFactory function will be used to calculate the upperLimit of the values that we’ll be checking for common multiplicity.

#### isCommonMultiple(range, num)

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.

```function isCommonMultiple(range, num) {
var reversed = range.reverse();
for (var i = 0 ; i < reversed.length ; i++) {
if(num % reversed[i] !== 0) {
return false;
}
}
return true;
}

isCommonMultiple([1,2,3,4,5], 24); // false
isCommonMultiple([1,2,3,4,5], 60); // true
```

#### 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 `1*2*3*4*5*6*7*8*9/(1*2*3*4)` or `9!/4!`.

After we’ve gotten our `numbersToCheck`, `smallestNum`, `largestNum` and `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:

```function smallestCommons(arr) {
var numbersToCheck = getRange(arr);
var smallestNum = arr.sort();
var largestNum = arr.sort();
var upperLimit = factorial(largestNum)/factorial(smallestNum - 1);
for (var i = largestNum ; i < upperLimit ; i = i + largestNum) {
if (isCommonMultiple(numbersToCheck, i)) {
return i;
}
}
return upperLimit;
}

function getRange(arr) {
var range = [];
for (var i = arr.sort() ; i <= arr.sort() ; i++) {
range.push(i);
}
return range;
}

function factorialFactory() {
var memo = {};

function factorialFunc(num) {
if (memo.hasOwnProperty(num)) {
console.log("from memory");
return memo[num];
} else {
var factorial = 1;
for (var i = 1; i <= num ; i++) {
factorial *= i;
memo[i] = factorial;
}
console.log("first time");
return factorial;
}
}

return factorialFunc;
}

var factorial = factorialFactory();

function isCommonMultiple(range, num) {
for (var i = 0 ; i < range.length ; i++) {
if(num % range[i] !== 0) {
return false;
}
}
return true;
}

smallestCommons([1,5]);
```

## Final Thoughts

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!

Also published on Medium.