Making Smallest Common Multiple more efficient

Making Smallest Common Multiple more efficient
0

#1

Here is my code:

function smallestCommons(arr) {
  let minNum = Math.min(...arr);
  let maxNum = Math.max(...arr);
  
  //fill out array
  for (let i = minNum+1; i<maxNum; i++) {
    arr.push(i);
  }

  let maxMultiple = arr.reduce((acc,next) => acc*next);

  for (let j = maxNum; j < maxMultiple; j+=maxNum) {
    if (arr.every(x => j % x === 0)) { return j;}
  }
  return maxMultiple;
}


smallestCommons([1,5]);

I am not passing the last test. Last time I went through the material, I remember having this problem. I cannot remember, though, what I did to avoid it (other than increment by maxNum rather than simply the incremental operator.

How can I fix this to make it efficient enough to pass the last test?


#2

This takes too many steps.

I solved this problem by using the Greatest Common Divisor - GCD.
If you multiply any two numbers, x times y, then divide the result by their GCD, then you obtain their Smallest Common Multiple.

There is a neat function that finds the GCD rather quickly. :slight_smile:


#3

Thanks. I’ll just use that solution. I’ve known about that approach, but I was trying to solve it without that formula. I’ve done it before (I’ve been reworking these Intermediate JS problems to get more proficient and quick at solving them), and I used an approach that approximates my approach above. I just can’t remember how I avoided it taking too long for the last problem.