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()[0] ; i <= arr.sort()[1] ; 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()[0];
  var largestNum = arr.sort()[1];
  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()[0] ; i <= arr.sort()[1] ; 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.

Leave a Reply

Your email address will not be published. Required fields are marked *