Smallest Common Multiple solution -efficient enough?

JavaScript
4

So spoilers here; I am not very knowledgeable w/r/t maths, so had to look this up, but:

  1. lowest common multiple of a and b (make it a function like lcm(a, b)) is equal to a times b divided by the greatest common divisor of a and b.
  2. So this looks like (a * b) / gcd(a, b).
  3. GCD is very easy to calculate:
    function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}
    (nb the [a, b] = [b, a] is an easy way to swap variables without using a temporary variable, I just used it to save space)
  4. Now, if you have a range of numbers low…high, you can just run the lcm function on the first two, then take the result of that and run it on that and the next number and so on. In other words, reduce.
function smallestCommons(arr) {
  return inclusiveRange(Math.min(...arr), Math.max(...arr)).reduce(lcm);
}

function inclusiveRange(a, b) {
  const range = [];
  for (let i = a; i <= b; i++) {
    range.push(i);
  }
  return range;
}

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b)
}

The performance will never be fantastic because the number of computations just explodes as you add more numbers to the range, but I think it should be pretty good - passes the tests no problem, and there’s no visible slowdown when I run the function in my browser.

Edit:

6 Likes