JavaScript Find Least Common Multiple

Question

Hey there, I could use some feedback on this code for Smallest Common Multiple Algorithm Challenge on FCC. I am stuck and can't get any further. I have created a function that will return the LCM for any two numbers for a specified array length. I don't know how to check to see if any of my multiples are in fact the LCM. Right now I just need some pointers to get me going in the right direction. Thanks for the help.
DIRECTIONS:
Find the smallest common multiple of the provided parameters that can be evenly divided by both, as well as by all sequential numbers in the range between these parameters.
The range will be an array of two numbers that will not necessarily be in numerical order.
e.g. for 1 and 3 - find the smallest common multiple of both 1 and 3 that is evenly divisible by all numbers between 1 and 3.
```JavaScript
function smallestCommons(arr) {
  arr = arr.sort(function(a, b){
    return a - b;
  });
  var arrRange = []; 
  var multiArr = []; 
  var min = Math.min(arr[0], arr[1]);
  var max = Math.max(arr[0], arr[1]); 
  var arrA = []; // array created to store all multiples of greatest number to check other LCM's                         against later
  var units = 20; // length that arrA will be. Need better way to find possible LCM's
//create all the missing numbers from arr[0] to arr[1];
  for (i = arr[0]; i <= arr[1]; i ++) {
    arrRange.push(i);
  }
//input any two numbers and it will return the LCM.
  function lcmArr(a, b) {
    var small;
    for (i = 1; i <= units; i ++) {
      arrA.push(i * a);
    }
for (i = 0; i < arrA.length; i ++) {
  if (arrA[i]%b === 0) {
    multiArr.push(arrA[i]); //creates all the multiples for a, b
  }
}

small = multiArr.shift(); // grabs the first index, which is the LCM for a, b
return small;   
  }
}
smallestCommons([1,5]);
```

miikis · Accepted Answer

Hey Trevor,
Even if your above algorithm worked, it'd still be pretty expensive, computationally. You could make your life drastically easier if you were to approach this problem from a mathematical perspective.
So, the Least Common Multiple (https://en.wikipedia.org/wiki/Least_common_multiple#Computing_the_least_common_multiple) of two numbers is equal to the product of those two numbers divided by the Greatest Common Divisor (https://en.wikipedia.org/wiki/Greatest_common_divisor) of those same two numbers. That's pretty great right there, no?  It's basically the answer to your problem, in O(1) no less. The LCM is equal to (a * b) / GCD(a, b)!!! Just kidding; you still have to figure out how to calculate the GCD of two numbers.
But, again, you're in luck; the mathematicians of yesteryear have all stood on each others shoulders just so we all could benefit from an efficient method of calculating the GCD of two numbers. This method is known as the Euclidean Algorithm (https://en.wikipedia.org/wiki/Euclidean_algorithm). You can read more about it in the Wiki, if you want, but essentially there's two versions of this algorithm: one that uses subtraction and one that uses division and remainders. The latter is more efficient; in fact, it's apparently so efficient that, given a pair of integers, your algorithm's number of steps will never be more than five times the number of digits of the smaller integer. That's pretty damn fast.
I'm gonna stop here and let you try and implement the rest on your own. Don't be afraid to use the Wiki. The LCM algorithm should now be pretty straight-forward. You're basically just returning a * b / gcd(a, b). Not that it really matters, but even that simple statement can be further optimized by only dividing a by gcd(a,b) and then multiplying that quotient by b, like so: a / gcd(a,b) * b. You'll also want to do some early returns that check if a and/or b are equal to zero. If only one of the two is zero, then you can just return the absolute-value of the other one; if both are zero, you can just return zero... because you can't divide by zero. Aiiight, I'm done. Let me know if you need help implementing that GCD :)

Welcome to the Treehouse Community

Looking to learn something new?

Trevor Johnson

Trevor Johnson

JavaScript Find Least Common Multiple

1 Answer

miikis

miikis